﻿// -------------------------------------------------------------------------
//    @FileName         :    TestNFShmHashTableWithList.h
//    @Author           :    gaoyi
//    @Date             :    2025/1/27
//    @Email            :    445267987@qq.com
//    @Module           :    TestNFShmHashTableWithList
//
// -------------------------------------------------------------------------

#pragma once

#include <gtest/gtest.h>
#include "NFComm/NFShmStl/NFShmHashTableWithList.h"
#include <string>
#include <functional>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <numeric>

// 测试用的简单键值对结构
struct TestPairWithList
{
    int key;
    std::string value;

    TestPairWithList() : key(0), value("")
    {
    }

    TestPairWithList(int k, const std::string& v) : key(k), value(v)
    {
    }

    bool operator==(const TestPairWithList& other) const
    {
        return key == other.key && value == other.value;
    }

    // 为支持 std::less 和 std::greater 添加比较运算符
    // 主要按 key 排序，key 相同时按 value 排序
    bool operator<(const TestPairWithList& other) const
    {
        if (key != other.key)
        {
            return key < other.key;
        }
        return value < other.value;
    }

    bool operator>(const TestPairWithList& other) const
    {
        return other < *this;
    }

    bool operator<=(const TestPairWithList& other) const
    {
        return !(other < *this);
    }

    bool operator>=(const TestPairWithList& other) const
    {
        return !(*this < other);
    }

    bool operator!=(const TestPairWithList& other) const
    {
        return !(*this == other);
    }
};

// 提取键的函数对象
struct ExtractKeyWithList
{
    int operator()(const TestPairWithList& pair) const
    {
        return pair.key;
    }
};

// 哈希函数对象
struct HashFuncWithList
{
    size_t operator()(int key) const
    {
        return std::hash<int>{}(key);
    }
};

// 键比较函数对象
struct EqualKeyWithList
{
    bool operator()(int key1, int key2) const
    {
        return key1 == key2;
    }
};

// 定义测试用的哈希表类型
using TestHashTableWithList = NFShmHashTableWithList<TestPairWithList, int, 50, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>;

// 定义大容量测试用的哈希表类型（用于性能测试）
using LargeTestHashTableWithList = NFShmHashTableWithList<TestPairWithList, int, 2000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>;

using MaxLargeTestHashTableWithList = NFShmHashTableWithList<TestPairWithList, int, 10000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>;

// ==================== 基础链表功能测试 ====================

TEST(NFShmHashTableWithListTest, BasicListConstruction)
{
    TestHashTableWithList ht;

    EXPECT_EQ(ht.size(), 0);
    EXPECT_EQ(ht.max_size(), 50);
    EXPECT_TRUE(ht.empty());
    EXPECT_FALSE(ht.full());
    EXPECT_FALSE(ht.is_lru_enabled()); // 默认应该禁用LRU

    // 测试空链表迭代器
    EXPECT_EQ(ht.list_begin(), ht.list_end());
    EXPECT_EQ(ht.list_cbegin(), ht.list_cend());
}

TEST(NFShmHashTableWithListTest, InsertionOrderMaintenance)
{
    TestHashTableWithList ht;

    // 按特定顺序插入元素
    std::vector<int> insert_order = {5, 1, 8, 3, 2, 7, 4, 6};
    for (int key : insert_order)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht.insert_unique(pair);
        EXPECT_TRUE(result.second);
    }

    ht.print_structure();

    EXPECT_EQ(ht.size(), insert_order.size());

    // 验证链表迭代器按插入顺序遍历
    auto list_iter = ht.list_begin();
    for (size_t i = 0; i < insert_order.size(); ++i)
    {
        EXPECT_NE(list_iter, ht.list_end());
        EXPECT_EQ(list_iter->key, insert_order[i]);
        EXPECT_EQ(list_iter->value, "value" + std::to_string(insert_order[i]));
        ++list_iter;
    }
    EXPECT_EQ(list_iter, ht.list_end());
}

TEST(NFShmHashTableWithListTest, ListIteratorTraversal)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {10, 20, 30, 40, 50};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 测试非常量迭代器
    std::vector<int> traversed_keys;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        traversed_keys.push_back(iter->key);
    }
    EXPECT_EQ(traversed_keys, keys);

    // 测试常量迭代器
    traversed_keys.clear();
    const auto& const_ht = ht;
    for (auto iter = const_ht.list_begin(); iter != const_ht.list_end(); ++iter)
    {
        traversed_keys.push_back(iter->key);
    }
    EXPECT_EQ(traversed_keys, keys);

    // 测试C++11风格常量迭代器
    traversed_keys.clear();
    for (auto iter = ht.list_cbegin(); iter != ht.list_cend(); ++iter)
    {
        traversed_keys.push_back(iter->key);
    }
    EXPECT_EQ(traversed_keys, keys);
}

TEST(NFShmHashTableWithListTest, ListAfterErase)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {1, 2, 3, 4, 5};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 删除中间元素
    ht.erase(3);

    // 验证链表顺序：应该是 1, 2, 4, 5
    std::vector<int> expected = {1, 2, 4, 5};
    std::vector<int> actual;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual.push_back(iter->key);
    }
    EXPECT_EQ(actual, expected);

    // 删除头元素
    ht.erase(1);
    expected = {2, 4, 5};
    actual.clear();
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual.push_back(iter->key);
    }
    EXPECT_EQ(actual, expected);

    // 删除尾元素
    ht.erase(5);
    expected = {2, 4};
    actual.clear();
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual.push_back(iter->key);
    }
    EXPECT_EQ(actual, expected);
}

// ==================== LRU功能测试 ====================

TEST(NFShmHashTableWithListTest, LRUEnableDisable)
{
    TestHashTableWithList ht;

    // 默认应该禁用LRU
    EXPECT_FALSE(ht.is_lru_enabled());

    // 启用LRU
    ht.enable_lru();
    EXPECT_TRUE(ht.is_lru_enabled());

    // 禁用LRU
    ht.disable_lru();
    EXPECT_FALSE(ht.is_lru_enabled());
}

TEST(NFShmHashTableWithListTest, LRUFindBehavior)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {1, 2, 3, 4, 5};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 在LRU禁用时，find不应该改变顺序
    ht.disable_lru();
    auto iter = ht.find(2);
    EXPECT_NE(iter, ht.end());

    // 验证顺序没有改变
    std::vector<int> order_after_find;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        order_after_find.push_back(list_iter->key);
    }
    EXPECT_EQ(order_after_find, keys); // 顺序应该不变

    // 启用LRU后，find应该将元素移动到尾部
    ht.enable_lru();
    iter = ht.find(2);
    EXPECT_NE(iter, ht.end());

    // 验证2被移动到了尾部，新顺序应该是 1, 3, 4, 5, 2
    std::vector<int> expected_order = {1, 3, 4, 5, 2};
    order_after_find.clear();
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        order_after_find.push_back(list_iter->key);
    }
    EXPECT_EQ(order_after_find, expected_order);
}

TEST(NFShmHashTableWithListTest, LRUCountBehavior)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {10, 20, 30, 40, 50};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    ht.enable_lru();

    // 使用count访问元素30
    size_t count = ht.count(30);
    EXPECT_EQ(count, 1);

    // 验证30被移动到了尾部
    std::vector<int> expected_order = {10, 20, 40, 50, 30};
    std::vector<int> actual_order;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        actual_order.push_back(list_iter->key);
    }
    EXPECT_EQ(actual_order, expected_order);
}

TEST(NFShmHashTableWithListTest, LRUMultipleAccesses)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {1, 2, 3, 4, 5};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    ht.enable_lru();

    // 按顺序访问：2, 4, 1
    ht.find(2); // 顺序变为: 1, 3, 4, 5, 2
    ht.find(4); // 顺序变为: 1, 3, 5, 2, 4
    ht.find(1); // 顺序变为: 3, 5, 2, 4, 1

    std::vector<int> expected_order = {3, 5, 2, 4, 1};
    std::vector<int> actual_order;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        actual_order.push_back(list_iter->key);
    }
    EXPECT_EQ(actual_order, expected_order);
}

TEST(NFShmHashTableWithListTest, LRUAccessNonexistentKey)
{
    TestHashTableWithList ht;

    // 插入测试数据
    std::vector<int> keys = {1, 2, 3};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    ht.enable_lru();

    // 访问不存在的键，不应该改变顺序
    auto iter = ht.find(999);
    EXPECT_EQ(iter, ht.end());

    std::vector<int> actual_order;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        actual_order.push_back(list_iter->key);
    }
    EXPECT_EQ(actual_order, keys); // 顺序应该保持不变
}

// ==================== 边界情况测试 ====================

TEST(NFShmHashTableWithListTest, SingleElementList)
{
    TestHashTableWithList ht;

    // 插入单个元素
    TestPairWithList pair(42, "answer");
    ht.insert_unique(pair);

    // 验证链表迭代器
    auto iter = ht.list_begin();
    EXPECT_NE(iter, ht.list_end());
    EXPECT_EQ(iter->key, 42);
    EXPECT_EQ(iter->value, "answer");

    ++iter;
    EXPECT_EQ(iter, ht.list_end());

    // 测试LRU访问单个元素
    ht.enable_lru();
    auto find_iter = ht.find(42);
    EXPECT_NE(find_iter, ht.end());

    // 单个元素的LRU访问不应该改变任何东西
    iter = ht.list_begin();
    EXPECT_EQ(iter->key, 42);
    ++iter;
    EXPECT_EQ(iter, ht.list_end());
}

TEST(NFShmHashTableWithListTest, ClearAndReset)
{
    TestHashTableWithList ht;

    // 插入数据并启用LRU
    for (int i = 1; i <= 10; ++i)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        ht.insert_unique(pair);
    }
    ht.enable_lru();

    // 清空哈希表
    ht.clear();

    EXPECT_EQ(ht.size(), 0);
    EXPECT_TRUE(ht.empty());
    EXPECT_EQ(ht.list_begin(), ht.list_end());

    // LRU设置应该保持
    EXPECT_TRUE(ht.is_lru_enabled());

    // 重新插入数据
    TestPairWithList pair(100, "new_value");
    ht.insert_unique(pair);

    auto iter = ht.list_begin();
    EXPECT_NE(iter, ht.list_end());
    EXPECT_EQ(iter->key, 100);
    ++iter;
    EXPECT_EQ(iter, ht.list_end());
}

TEST(NFShmHashTableWithListTest, InsertEqual)
{
    TestHashTableWithList ht;

    // 插入重复键的元素
    TestPairWithList pair1(1, "first");
    TestPairWithList pair2(1, "second");
    TestPairWithList pair3(1, "third");

    ht.insert_equal(pair1);
    ht.insert_equal(pair2);
    ht.insert_equal(pair3);

    EXPECT_EQ(ht.size(), 3);
    EXPECT_EQ(ht.count(1), 3);

    // 验证插入顺序维护
    std::vector<std::string> expected_values = {"first", "second", "third"};
    std::vector<std::string> actual_values;

    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        if (iter->key == 1)
        {
            actual_values.push_back(iter->value);
        }
    }

    EXPECT_EQ(actual_values, expected_values);
}

// ==================== 复制和赋值测试 ====================

TEST(NFShmHashTableWithListTest, CopyConstructor)
{
    TestHashTableWithList ht1;

    // 在ht1中插入数据并设置LRU
    std::vector<int> keys = {1, 2, 3, 4, 5};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht1.insert_unique(pair);
    }
    ht1.enable_lru();

    // 访问一些元素改变LRU顺序
    ht1.find(3);
    ht1.find(1);

    // 复制构造
    TestHashTableWithList ht2(ht1);

    // 验证大小和LRU设置
    EXPECT_EQ(ht2.size(), ht1.size());
    EXPECT_EQ(ht2.is_lru_enabled(), ht1.is_lru_enabled());

    // 验证插入顺序一致
    std::vector<int> order1, order2;
    for (auto iter = ht1.list_begin(); iter != ht1.list_end(); ++iter)
    {
        order1.push_back(iter->key);
    }
    for (auto iter = ht2.list_begin(); iter != ht2.list_end(); ++iter)
    {
        order2.push_back(iter->key);
    }
    EXPECT_EQ(order1, order2);
}

TEST(NFShmHashTableWithListTest, AssignmentOperator)
{
    TestHashTableWithList ht1, ht2;

    // 在ht1中插入数据
    for (int i = 10; i <= 50; i += 10)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        ht1.insert_unique(pair);
    }
    ht1.enable_lru();

    // 在ht2中插入不同的数据
    for (int i = 1; i <= 3; ++i)
    {
        TestPairWithList pair(i, "old_value" + std::to_string(i));
        ht2.insert_unique(pair);
    }

    // 赋值操作
    ht2 = ht1;

    // 验证ht2现在与ht1相同
    EXPECT_EQ(ht2.size(), ht1.size());
    EXPECT_EQ(ht2.is_lru_enabled(), ht1.is_lru_enabled());

    // 验证链表顺序一致
    auto iter1 = ht1.list_begin();
    auto iter2 = ht2.list_begin();
    while (iter1 != ht1.list_end() && iter2 != ht2.list_end())
    {
        EXPECT_EQ(iter1->key, iter2->key);
        EXPECT_EQ(iter1->value, iter2->value);
        ++iter1;
        ++iter2;
    }
    EXPECT_EQ(iter1, ht1.list_end());
    EXPECT_EQ(iter2, ht2.list_end());
}

// ==================== 性能和容量测试 ====================

TEST(NFShmHashTableWithListTest, FullCapacityInsertion)
{
    TestHashTableWithList ht;

    // 填满哈希表
    for (int i = 1; i <= 50; ++i)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        auto result = ht.insert_unique(pair);
        EXPECT_TRUE(result.second);
    }

    EXPECT_EQ(ht.size(), 50);
    EXPECT_TRUE(ht.full());
    EXPECT_EQ(ht.left_size(), 0);

    // 验证所有元素都在链表中
    std::set<int> expected_keys;
    for (int i = 1; i <= 50; ++i)
    {
        expected_keys.insert(i);
    }

    std::set<int> actual_keys;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual_keys.insert(iter->key);
    }

    EXPECT_EQ(actual_keys, expected_keys);

    // 尝试插入更多元素应该失败
    TestPairWithList extra_pair(51, "extra");
    auto result = ht.insert_unique(extra_pair);
    EXPECT_FALSE(result.second);
    EXPECT_EQ(ht.size(), 50);
}

// ==================== 打印功能测试 ====================

TEST(NFShmHashTableWithListTest, PrintFunctions)
{
    TestHashTableWithList ht;

    // 插入一些数据
    std::vector<int> keys = {15, 25, 35};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }
    ht.enable_lru();

    // 这些函数主要用于调试，我们只是确保它们不会崩溃
    EXPECT_NO_THROW(ht.print_structure());
    EXPECT_NO_THROW(ht.print_list());
    EXPECT_NO_THROW(ht.print_detailed());
    EXPECT_NO_THROW(ht.print_simple());

    // 测试空表的打印
    TestHashTableWithList empty_ht;
    EXPECT_NO_THROW(empty_ht.print_structure());
    EXPECT_NO_THROW(empty_ht.print_list());
}

// ==================== 链表完整性测试 ====================

TEST(NFShmHashTableWithListTest, ListIntegrityAfterOperations)
{
    TestHashTableWithList ht;

    // 插入、删除、再插入的混合操作
    for (int i = 1; i <= 10; ++i)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        ht.insert_unique(pair);
    }

    // 删除一些元素
    ht.erase(3);
    ht.erase(7);
    ht.erase(1);

    // 再插入一些新元素
    TestPairWithList pair11(11, "value11");
    TestPairWithList pair12(12, "value12");
    ht.insert_unique(pair11);
    ht.insert_unique(pair12);

    // 验证链表的完整性
    std::vector<int> expected_keys;
    for (auto iter = ht.begin(); iter != ht.end(); ++iter)
    {
        expected_keys.push_back(iter->key);
    }
    std::sort(expected_keys.begin(), expected_keys.end());

    std::vector<int> list_keys;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        list_keys.push_back(iter->key);
    }
    std::sort(list_keys.begin(), list_keys.end());

    // 链表中的键应该与哈希表中的键完全一致
    EXPECT_EQ(list_keys, expected_keys);
    EXPECT_EQ(ht.size(), list_keys.size());
}

// ==================== equal_range LRU功能测试 ====================

TEST(NFShmHashTableWithListTest, EqualRangeLRUBehavior)
{
    TestHashTableWithList ht;

    // 插入一些测试数据，包括重复的键
    std::vector<int> keys = {1, 2, 1, 3, 2, 4, 1}; // 键1有3个，键2有2个
    for (size_t i = 0; i < keys.size(); ++i)
    {
        TestPairWithList pair(keys[i], "value" + std::to_string(i));
        ht.insert_equal(pair);
    }

    EXPECT_EQ(ht.size(), 7);

    // 启用LRU功能
    ht.enable_lru();
    EXPECT_TRUE(ht.is_lru_enabled());

    // 记录查询前的插入顺序
    std::vector<int> order_before_query;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        order_before_query.push_back(it->key);
    }

    printf("\n=== equal_range LRU Test ===\n");
    printf("Before equal_range query - insertion order: ");
    for (int k : order_before_query)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 使用 equal_range 查询键1（应该有3个匹配元素）
    auto range = ht.equal_range(1);

    // 验证找到的元素
    int count = 0;
    for (auto it = range.first; it != range.second; ++it)
    {
        EXPECT_EQ(it->key, 1);
        count++;
    }
    EXPECT_GT(count, 0); // 应该找到至少一个元素

    // 记录查询后的插入顺序
    std::vector<int> order_after_query;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        order_after_query.push_back(it->key);
    }

    printf("After equal_range query - insertion order: ");
    for (int k : order_after_query)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 验证LRU行为：被查询的键1的元素应该移动到链表尾部
    // 统计链表尾部连续的键1元素数量
    int trailing_ones = 0;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        if (it->key == 1)
        {
            // 找到第一个键1，计算从这里到尾部有多少个键1
            auto temp_it = it;
            int consecutive_ones = 0;
            while (temp_it != ht.list_end() && temp_it->key == 1)
            {
                consecutive_ones++;
                ++temp_it;
            }
            if (temp_it == ht.list_end()) // 到达了链表尾部
            {
                trailing_ones = consecutive_ones;
            }
            break;
        }
    }

    printf("Trailing consecutive key=1 elements: %d\n", trailing_ones);

    // 验证至少有一些键1的元素被移到了尾部
    EXPECT_GT(trailing_ones, 0);

    // 测试常量版本的equal_range
    const auto& const_ht = ht;
    auto const_range = const_ht.equal_range(2);

    // 验证常量版本也能找到元素
    int const_count = 0;
    for (auto it = const_range.first; it != const_range.second; ++it)
    {
        EXPECT_EQ(it->key, 2);
        const_count++;
    }
    EXPECT_GT(const_count, 0);

    // 禁用LRU并再次测试
    ht.disable_lru();
    EXPECT_FALSE(ht.is_lru_enabled());

    // 记录禁用LRU前的顺序
    std::vector<int> order_before_disabled;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        order_before_disabled.push_back(it->key);
    }

    // 查询键3（只有1个）
    auto range_disabled = ht.equal_range(3);

    // 记录禁用LRU后的顺序
    std::vector<int> order_after_disabled;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        order_after_disabled.push_back(it->key);
    }

    // 禁用LRU后，顺序应该保持不变
    EXPECT_EQ(order_before_disabled, order_after_disabled);

    printf("LRU disabled - order unchanged: %s\n", (order_before_disabled == order_after_disabled) ? "Yes" : "No");
    printf("========================\n");
}

// ==================== 链表头部插入功能测试 ====================

TEST(NFShmHashTableWithListTest, InsertToHead)
{
    TestHashTableWithList ht;

    // 测试默认插入模式（尾部插入）
    EXPECT_FALSE(ht.is_insert_head_enable()); // 默认应该是尾部插入

    // 插入一些元素，验证尾部插入顺序
    std::vector<int> keys = {1, 2, 3, 4, 5};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 验证插入顺序（应该按插入顺序 1, 2, 3, 4, 5）
    std::vector<int> tail_insert_order;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        tail_insert_order.push_back(iter->key);
    }
    EXPECT_EQ(tail_insert_order, keys);

    printf("\n=== Insert To Head Test ===\n");
    printf("Tail insert order: ");
    for (int k : tail_insert_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 清空哈希表并启用头部插入
    ht.clear();
    ht.enable_insert_head();
    EXPECT_TRUE(ht.is_insert_head_enable());

    // 重新插入相同的元素，这次应该是头部插入
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 验证头部插入顺序（应该是逆序 5, 4, 3, 2, 1）
    std::vector<int> head_insert_order;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        head_insert_order.push_back(iter->key);
    }

    std::vector<int> expected_head_order = {5, 4, 3, 2, 1};
    EXPECT_EQ(head_insert_order, expected_head_order);

    printf("Head insert order: ");
    for (int k : head_insert_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 测试混合插入：先几个元素，然后切换模式，再插入几个元素
    ht.clear();
    ht.disable_insert_head(); // 重新设置为尾部插入

    // 先插入1, 2（尾部插入）
    ht.insert_unique(TestPairWithList(1, "value1"));
    ht.insert_unique(TestPairWithList(2, "value2"));

    // 切换到头部插入
    ht.enable_insert_head();

    // 再插入3, 4（头部插入）
    ht.insert_unique(TestPairWithList(3, "value3"));
    ht.insert_unique(TestPairWithList(4, "value4"));

    // 验证混合插入结果：应该是 4, 3, 1, 2
    std::vector<int> mixed_order;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        mixed_order.push_back(iter->key);
    }

    std::vector<int> expected_mixed_order = {4, 3, 1, 2};
    EXPECT_EQ(mixed_order, expected_mixed_order);

    printf("Mixed insert order: ");
    for (int k : mixed_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    printf("========================\n");
}

TEST(NFShmHashTableWithListTest, InsertToHeadWithLRU)
{
    TestHashTableWithList ht;

    // 启用头部插入和LRU
    ht.enable_insert_head();
    ht.enable_lru();

    EXPECT_TRUE(ht.is_insert_head_enable());
    EXPECT_TRUE(ht.is_lru_enabled());

    // 插入测试数据
    std::vector<int> keys = {10, 20, 30};
    for (int key : keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    printf("\n=== Insert To Head With LRU Test ===\n");

    // 记录插入后的顺序（头部插入应该是 30, 20, 10）
    std::vector<int> insert_order;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        insert_order.push_back(iter->key);
    }

    std::vector<int> expected_insert_order = {30, 20, 10};
    EXPECT_EQ(insert_order, expected_insert_order);

    printf("After head insert: ");
    for (int k : insert_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 使用LRU访问中间元素20
    auto iter = ht.find(20);
    EXPECT_NE(iter, ht.end());
    EXPECT_EQ(iter->key, 20);

    // 验证LRU访问后的顺序（20应该移到头部：20, 30, 10）
    // 因为enable_insert_head为true，LRU访问将元素移到头部
    std::vector<int> lru_order;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        lru_order.push_back(list_iter->key);
    }

    std::vector<int> expected_lru_order = {20, 30, 10};
    EXPECT_EQ(lru_order, expected_lru_order);

    printf("After LRU access: ");
    for (int k : lru_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    // 再插入一个新元素，应该插入到头部
    ht.insert_unique(TestPairWithList(40, "value40"));

    // 验证新元素插入到头部：40, 20, 30, 10
    // 40插入到头部，之前的顺序是20, 30, 10
    std::vector<int> final_order;
    for (auto list_iter = ht.list_begin(); list_iter != ht.list_end(); ++list_iter)
    {
        final_order.push_back(list_iter->key);
    }

    std::vector<int> expected_final_order = {40, 20, 30, 10};
    EXPECT_EQ(final_order, expected_final_order);

    printf("After insert new: ");
    for (int k : final_order)
    {
        printf("%d ", k);
    }
    printf("\n");

    printf("=============================\n");
}

TEST(NFShmHashTableWithListTest, InsertToHeadIntegrity)
{
    TestHashTableWithList ht;

    // 启用头部插入
    ht.enable_insert_head();

    // 插入大量元素测试完整性
    const int NUM_ELEMENTS = 30;
    for (int i = 1; i <= NUM_ELEMENTS; ++i)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        auto result = ht.insert_unique(pair);
        EXPECT_TRUE(result.second);
    }

    EXPECT_EQ(ht.size(), NUM_ELEMENTS);

    // 验证链表完整性
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 验证头部插入顺序（应该是逆序）
    std::vector<int> actual_order;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual_order.push_back(iter->key);
    }

    // 预期顺序：30, 29, 28, ..., 2, 1
    std::vector<int> expected_order;
    for (int i = NUM_ELEMENTS; i >= 1; --i)
    {
        expected_order.push_back(i);
    }

    EXPECT_EQ(actual_order, expected_order);

    // 测试删除操作不影响链表完整性
    for (int i = 1; i <= NUM_ELEMENTS; i += 3) // 删除 1, 4, 7, 10, ...
    {
        ht.erase(i);
    }

    // 验证删除后的链表完整性
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 验证哈希表和链表的元素数量一致
    size_t hash_count = 0;
    for (auto iter = ht.begin(); iter != ht.end(); ++iter)
    {
        hash_count++;
    }

    size_t list_count = 0;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        list_count++;
    }

    EXPECT_EQ(hash_count, list_count);
    EXPECT_EQ(hash_count, ht.size());
}

TEST(NFShmHashTableWithListTest, InsertToHeadWithDuplicates)
{
    TestHashTableWithList ht;

    // 启用头部插入
    ht.enable_insert_head();

    // 使用insert_equal插入重复键
    std::vector<std::pair<int, std::string>> test_data = {{1, "first1"}, {2, "first2"}, {1, "second1"}, {3, "first3"}, {1, "third1"}, {2, "second2"}};

    for (const auto& data : test_data)
    {
        TestPairWithList pair(data.first, data.second);
        ht.insert_equal(pair);
    }

    printf("\n=== Insert To Head With Duplicates Test ===\n");

    // 验证插入顺序（头部插入，所以是逆序）
    std::vector<std::string> actual_values;
    for (auto iter = ht.list_begin(); iter != ht.list_end(); ++iter)
    {
        actual_values.push_back(iter->value);
    }

    // 预期顺序（头部插入的逆序）：second2, third1, first3, second1, first2, first1
    std::vector<std::string> expected_values = {"second2", "third1", "first3", "second1", "first2", "first1"};

    EXPECT_EQ(actual_values, expected_values);

    printf("Insert order (head insertion): ");
    for (const auto& v : actual_values)
    {
        printf("%s ", v.c_str());
    }
    printf("\n");

    // 验证各个键的数量
    EXPECT_EQ(ht.count(1), 3);
    EXPECT_EQ(ht.count(2), 2);
    EXPECT_EQ(ht.count(3), 1);

    printf("Key counts: key=1:%zu, key=2:%zu, key=3:%zu\n", ht.count(1), ht.count(2), ht.count(3));

    printf("=======================================\n");
}

/**
 * @brief 测试链表排序功能（使用类似NFShmList的sort接口）
 * @note 测试sort函数的各种场景：升序、降序、空链表、单元素、插入排序算法
 */
TEST(NFShmHashTableWithListTest, SortTest)
{
    printf("========== SortTest ==========\n");

    TestHashTableWithList ht;
    ht.CreateInit();

    // 测试1：空链表排序（默认比较器）
    printf("Test 1: Sorting empty list with default comparator\n");
    ht.SortListInsert(); // 使用默认比较器
    EXPECT_EQ(ht.size(), 0);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试2：单元素链表排序
    printf("Test 2: Sorting single element list\n");
    TestPairWithList pair1(42, "value42");
    ht.insert_unique(pair1);
    ht.SortListInsert(); // 使用默认比较器
    EXPECT_EQ(ht.size(), 1);
    EXPECT_EQ(ht.list_begin()->key, 42);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试3：多元素默认升序排序
    printf("Test 3: Default ascending sort (std::less)\n");
    ht.clear();
    std::vector<int> unsorted_keys = {5, 2, 8, 1, 9, 3};
    for (int key : unsorted_keys)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    printf("Before sorting: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("%d ", it->key);
    }
    printf("\n");

    // 默认升序排序
    ht.SortListInsert(); // 使用默认比较器 std::less<TestPairWithList>

    printf("After default sort: ");
    std::vector<int> ascending_result;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        ascending_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    std::vector<int> expected_ascending = {1, 2, 3, 5, 8, 9};
    printf("Expected: ");
    for (int val : expected_ascending)
        printf("%d ", val);
    printf("\n");

    // 详细验证
    EXPECT_EQ(ascending_result.size(), expected_ascending.size());
    for (size_t i = 0; i < ascending_result.size() && i < expected_ascending.size(); ++i)
    {
        if (ascending_result[i] != expected_ascending[i])
        {
            printf("Mismatch at index %zu: got %d, expected %d\n", i, ascending_result[i], expected_ascending[i]);
        }
        EXPECT_EQ(ascending_result[i], expected_ascending[i]);
    }
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 验证哈希表功能仍然正常
    for (int key : unsorted_keys)
    {
        auto iter = ht.find(key);
        EXPECT_NE(iter, ht.end());
        EXPECT_EQ(iter->key, key);
    }

    // 测试4：自定义比较器降序排序
    printf("Test 4: Custom comparator descending sort\n");
    ht.SortListInsert(std::greater<TestPairWithList>()); // 使用 std::greater

    printf("After descending sort: ");
    std::vector<int> descending_result;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        descending_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    std::vector<int> expected_descending = {9, 8, 5, 3, 2, 1};
    EXPECT_EQ(descending_result, expected_descending);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试5：幂等性 - 已排序的列表再次排序
    printf("Test 5: Idempotency - sorting already sorted list\n");
    ht.SortListInsert(std::greater<TestPairWithList>()); // 再次使用相同的降序排序

    printf("After sorting already sorted list: ");
    std::vector<int> idempotent_result;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        idempotent_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    EXPECT_EQ(idempotent_result, expected_descending);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试6：lambda表达式比较器（按奇偶性排序）
    printf("Test 6: Lambda expression comparator - sort by parity (even first, then odd)\n");
    ht.SortListInsert([](const TestPairWithList& a, const TestPairWithList& b)
    {
        // 偶数优先，同奇偶性时按值升序
        if ((a.key % 2) != (b.key % 2))
        {
            return (a.key % 2) == 0; // 偶数返回true（排在前面）
        }
        return a.key < b.key; // 同奇偶性时按值升序
    });

    printf("After parity sort (even first): ");
    std::vector<int> parity_result;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        parity_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    // 应该是：偶数{2, 8}在前，奇数{1, 3, 5, 9}在后
    std::vector<int> expected_parity = {2, 8, 1, 3, 5, 9};
    EXPECT_EQ(parity_result, expected_parity);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试7：大数据集插入排序性能测试
    printf("Test 7: Large dataset insertion sort performance test\n");
    ht.clear();
    const int LARGE_SIZE = 50;
    std::vector<int> large_keys;

    // 生成随机顺序的键
    for (int i = LARGE_SIZE; i > 0; --i)
    {
        large_keys.push_back(i);
        TestPairWithList pair(i, "value" + std::to_string(i));
        ht.insert_unique(pair);
    }

    printf("Large dataset size: %d elements\n", LARGE_SIZE);

    // 插入排序性能测试
    auto start = std::chrono::high_resolution_clock::now();
    ht.SortListInsert(); // 使用默认插入排序
    auto end = std::chrono::high_resolution_clock::now();

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    printf("Insertion sort completed in %lld microseconds\n", duration.count());

    // 验证排序结果
    int prev_key = 0;
    bool is_sorted = true;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        if (it->key <= prev_key)
        {
            is_sorted = false;
            break;
        }
        prev_key = it->key;
    }

    EXPECT_TRUE(is_sorted);
    EXPECT_EQ(ht.size(), LARGE_SIZE);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    printf("Large dataset sort completed successfully\n");

    // 测试8：函数对象比较器
    printf("Test 8: Function object comparator\n");
    struct KeyComparator
    {
        bool operator()(const TestPairWithList& a, const TestPairWithList& b) const
        {
            return a.key > b.key; // 降序
        }
    };

    ht.SortListInsert(KeyComparator());

    printf("After function object sort (descending): ");
    std::vector<int> funcObjSorted;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("%d ", it->key);
        funcObjSorted.push_back(it->key);
    }
    printf("\n");

    // 应该是降序
    bool isDescending = true;
    for (size_t i = 1; i < funcObjSorted.size(); ++i)
    {
        if (funcObjSorted[i] > funcObjSorted[i - 1])
        {
            isDescending = false;
            break;
        }
    }
    EXPECT_TRUE(isDescending);
    EXPECT_TRUE(ht.ValidateListIntegrity());

    // 测试9：验证比较运算符正确性（测试key和value的综合排序）
    printf("Test 9: Operator comparator correctness with key and value sorting\n");
    ht.clear();

    // 插入不同的元素来测试按key主排序，value次排序
    ht.insert_unique(TestPairWithList(3, "value_c"));
    ht.insert_unique(TestPairWithList(1, "value_z"));
    ht.insert_unique(TestPairWithList(2, "value_a"));

    printf("Before sort (mixed keys and values): ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
    }
    printf("\n");

    ht.SortListInsert(); // 使用默认比较器，按key排序

    printf("After sort (by key primarily): ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
    }
    printf("\n");

    // 验证排序：应该按key升序排列 (1,value_z), (2,value_a), (3,value_c)
    auto iter = ht.list_begin();
    EXPECT_EQ(iter->key, 1);
    EXPECT_EQ(iter->value, "value_z");
    ++iter;
    EXPECT_EQ(iter->key, 2);
    EXPECT_EQ(iter->value, "value_a");
    ++iter;
    EXPECT_EQ(iter->key, 3);
    EXPECT_EQ(iter->value, "value_c");

    EXPECT_TRUE(ht.ValidateListIntegrity());

    printf("==================================\n");
}

/**
 * @brief 大数据量排序性能和正确性测试
 * @note 测试插入排序在不同数据规模下的性能和正确性
 */
TEST(NFShmHashTableWithListTest, LargeDataSortTest)
{
    printf("========== Large Data Sort Test ==========\n");

    // 测试1：中等规模数据（40个元素）
    printf("Test 1: Medium scale sorting (40 elements)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int MEDIUM_SIZE = 40;
        std::vector<int> random_keys;

        // 生成随机数据
        for (int i = 0; i < MEDIUM_SIZE; ++i)
        {
            random_keys.push_back(rand() % 1000);
        }

        // 插入数据
        for (int key : random_keys)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            if (ht.insert_unique(pair).second)
            {
                // 插入成功
            }
        }

        printf("Inserted %zu elements\n", ht.size());

        // 排序并计时
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Medium scale sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int prev_key = -1;
        bool is_sorted = true;
        size_t count = 0;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key < prev_key)
            {
                is_sorted = false;
                printf("Sort error at position %zu: %d < %d\n", count, it->key, prev_key);
                break;
            }
            prev_key = it->key;
            count++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_TRUE(ht.ValidateListIntegrity());

        // 验证哈希表功能仍然正常
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            auto found = ht.find(it->key);
            EXPECT_NE(found, ht.end());
            EXPECT_EQ(found->key, it->key);
        }

        printf("Medium scale test passed: %zu elements sorted correctly\n", ht.size());
    }

    // 测试2：大规模数据（50个元素）
    printf("\nTest 2: Large scale sorting (50 elements)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int LARGE_SIZE = 50;
        std::vector<int> sequence_keys;

        // 生成倒序序列
        for (int i = LARGE_SIZE; i > 0; --i)
        {
            sequence_keys.push_back(i);
        }

        // 插入数据
        for (int key : sequence_keys)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Inserted %zu elements (reverse order)\n", ht.size());

        // 排序并计时
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Large scale sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果（应该是升序排列）
        int prev_key = 0;
        bool is_sorted = true;
        std::vector<int> sorted_keys;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key < prev_key)
            {
                is_sorted = false;
                printf("Sort error: %d < %d (not in ascending order)\n", it->key, prev_key);
                break;
            }
            sorted_keys.push_back(it->key);
            prev_key = it->key;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(sorted_keys.size(), LARGE_SIZE);

        // 验证我们有完整的1到50序列
        std::vector<int> expected_sequence;
        for (int i = 1; i <= LARGE_SIZE; ++i)
        {
            expected_sequence.push_back(i);
        }
        EXPECT_EQ(sorted_keys, expected_sequence);

        EXPECT_TRUE(ht.ValidateListIntegrity());

        printf("Large scale test passed: %d elements sorted correctly\n", LARGE_SIZE);
    }

    // 测试3：洗牌数据排序（45个元素）
    printf("\nTest 3: Shuffled data sorting (45 elements)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int SHUFFLE_SIZE = 45;
        std::vector<int> shuffle_keys;

        // 生成洗牌序列
        for (int i = 1; i <= SHUFFLE_SIZE; ++i)
        {
            shuffle_keys.push_back(i);
        }
        std::random_shuffle(shuffle_keys.begin(), shuffle_keys.end());

        // 插入数据
        for (int key : shuffle_keys)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Inserted %zu elements (shuffled order)\n", ht.size());

        // 排序并计时
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Shuffled data sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int expected_key = 1;
        bool is_sorted = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key != expected_key)
            {
                is_sorted = false;
                printf("Sort error: expected %d, got %d\n", expected_key, it->key);
                break;
            }
            expected_key++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(expected_key - 1, SHUFFLE_SIZE);
        EXPECT_TRUE(ht.ValidateListIntegrity());

        printf("Shuffled data test passed: %d elements sorted correctly\n", SHUFFLE_SIZE);
    }

    // 测试4：已排序数据性能测试（最佳情况）
    printf("\nTest 4: Already sorted data performance test (best case)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int SORTED_SIZE = 48;

        // 插入已排序数据
        for (int i = 1; i <= SORTED_SIZE; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        printf("Inserted %d elements (already sorted)\n", SORTED_SIZE);

        // 排序并计时（应该很快，因为是最佳情况）
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Already sorted data sort completed in %lld microseconds\n", duration.count());

        // 验证仍然有序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Already sorted test passed: %d elements\n", SORTED_SIZE);
    }

    // 测试5：重复元素排序测试
    printf("\nTest 5: Duplicate elements sorting test\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int DUPLICATE_SIZE = 30;

        // 插入重复数据（每个值重复多次，但key不同）
        for (int i = 0; i < DUPLICATE_SIZE; ++i)
        {
            int value = i % 10; // 创建重复值
            TestPairWithList pair(i, "value" + std::to_string(value));
            ht.insert_unique(pair);
        }

        printf("Inserted %d elements with duplicate values\n", DUPLICATE_SIZE);

        // 按value排序
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if (a.value != b.value)
            {
                return a.value < b.value;
            }
            return a.key < b.key; // value相同时按key排序
        });
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Duplicate elements sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果（稳定排序，相同value的元素按key排序）
        std::string prev_value = "";
        int prev_key_for_same_value = -1;
        bool is_stable_sorted = true;

        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->value == prev_value)
            {
                if (it->key <= prev_key_for_same_value)
                {
                    is_stable_sorted = false;
                    printf("Stable sort error: value=%s, key=%d <= prev_key=%d\n", it->value.c_str(), it->key, prev_key_for_same_value);
                    break;
                }
            }
            else if (it->value < prev_value)
            {
                is_stable_sorted = false;
                printf("Sort error: value=%s < prev_value=%s\n", it->value.c_str(), prev_value.c_str());
                break;
            }

            prev_value = it->value;
            prev_key_for_same_value = it->key;
        }

        EXPECT_TRUE(is_stable_sorted);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Duplicate elements test passed: stable sorting verified\n");
    }

    // 测试6：性能对比测试（不同规模）
    printf("\nTest 6: Performance comparison across different scales\n");
    {
        std::vector<int> sizes = {10, 20, 30, 40, 50};
        std::vector<long long> times;

        for (int size : sizes)
        {
            TestHashTableWithList ht;
            ht.CreateInit();

            // 生成随机数据
            for (int i = 0; i < size; ++i)
            {
                int key = rand() % (size * 10);
                TestPairWithList pair(key, "value" + std::to_string(key));
                ht.insert_unique(pair);
            }

            // 排序并计时
            auto start = std::chrono::high_resolution_clock::now();
            ht.SortListInsert();
            auto end = std::chrono::high_resolution_clock::now();
            auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
            times.push_back(duration.count());

            printf("Size %d: %lld microseconds\n", size, duration.count());
            EXPECT_TRUE(ht.ValidateListIntegrity());
        }

        // 验证时间复杂度大致为O(n平方)（插入排序的预期复杂度）
        for (size_t i = 1; i < sizes.size(); ++i)
        {
            double ratio = (double)times[i] / times[i - 1];
            double size_ratio = (double)sizes[i] / sizes[i - 1];
            printf("Time ratio for size %d->%d: %.2f (expected ~%.2f for O(n平方))\n", sizes[i - 1], sizes[i], ratio, size_ratio * size_ratio);
        }
    }

    printf("========== Large Data Sort Test Completed ==========\n");
}

/**
 * @brief 排序边界情况和压力测试
 * @note 测试各种边界情况和极端场景
 */
TEST(NFShmHashTableWithListTest, SortEdgeCasesAndStressTest)
{
    printf("========== Sort Edge Cases and Stress Test ==========\n");

    // 测试1：两个元素排序
    printf("Test 1: Two elements sorting\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        ht.insert_unique(TestPairWithList(2, "second"));
        ht.insert_unique(TestPairWithList(1, "first"));

        ht.SortListInsert();

        auto it = ht.list_begin();
        EXPECT_EQ(it->key, 1);
        ++it;
        EXPECT_EQ(it->key, 2);

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Two elements test passed\n");
    }

    // 测试2：倒序排序（最坏情况）
    printf("Test 2: Reverse order sorting (worst case)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int REVERSE_SIZE = 35;

        // 插入完全倒序的数据
        for (int i = REVERSE_SIZE; i >= 1; --i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Reverse order sort (%d elements) completed in %lld microseconds\n", REVERSE_SIZE, duration.count());

        // 验证结果
        int expected = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected);
            expected++;
        }

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Reverse order test passed\n");
    }

    // 测试3：部分排序数据
    printf("Test 3: Partially sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入部分有序的数据：1,2,3,4,5, 10,9,8,7,6, 11,12,13,14,15
        std::vector<int> partial_sorted = {1, 2, 3, 4, 5, 10, 9, 8, 7, 6, 11, 12, 13, 14, 15};

        for (int key : partial_sorted)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Partially sorted data completed in %lld microseconds\n", duration.count());

        // 验证结果
        std::vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
        size_t i = 0;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it, ++i)
        {
            EXPECT_EQ(it->key, expected[i]);
        }

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Partially sorted test passed\n");
    }

    // 测试4：大量重复键值
    printf("Test 4: Many duplicate keys\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int DUPLICATE_COUNT = 5;

        // 插入重复的值（但键不同）
        for (int i = 0; i < DUPLICATE_COUNT; ++i)
        {
            for (int key = 1; key <= 10; ++key)
            {
                TestPairWithList pair(key * 10 + i, "value" + std::to_string(key));
                ht.insert_unique(pair);
            }
        }

        printf("Inserted %zu unique elements\n", ht.size());

        // 按value排序（会有很多重复的value）
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if (a.value != b.value)
            {
                return a.value < b.value;
            }
            return a.key < b.key;
        });
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Duplicate values sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        std::string prev_value = "";
        int prev_key = -1;
        bool is_sorted = true;

        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->value < prev_value || (it->value == prev_value && it->key <= prev_key))
            {
                is_sorted = false;
                break;
            }
            prev_value = it->value;
            prev_key = it->key;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Duplicate values test passed\n");
    }

    // 测试5：交替模式数据
    printf("Test 5: Alternating pattern data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        const int PATTERN_SIZE = 30;

        // 插入交替模式的数据：1,30,2,29,3,28,...
        for (int i = 1; i <= PATTERN_SIZE / 2; ++i)
        {
            TestPairWithList pair1(i, "small" + std::to_string(i));
            TestPairWithList pair2(PATTERN_SIZE - i + 1, "large" + std::to_string(PATTERN_SIZE - i + 1));
            ht.insert_unique(pair1);
            ht.insert_unique(pair2);
        }

        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Alternating pattern sort completed in %lld microseconds\n", duration.count());

        // 验证结果
        int expected = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected);
            expected++;
        }

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Alternating pattern test passed\n");
    }

    // 测试6：自定义复杂比较器
    printf("Test 6: Complex custom comparator\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据
        for (int i = 1; i <= 50; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i % 10));
            ht.insert_unique(pair);
        }

        // 复杂比较器：首先按value长度，然后按value字典序，最后按key
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if (a.value.length() != b.value.length())
            {
                return a.value.length() < b.value.length();
            }
            if (a.value != b.value)
            {
                return a.value < b.value;
            }
            return a.key < b.key;
        });
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("Complex comparator sort completed in %lld microseconds\n", duration.count());

        // 验证排序正确性（按复杂规则）
        auto prev_it = ht.list_begin();
        bool is_sorted = true;

        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it != ht.list_begin())
            {
                bool correct_order = (prev_it->value.length() < it->value.length()) || (prev_it->value.length() == it->value.length() && prev_it->value < it->value) || (prev_it->value.length() == it->value.length() && prev_it->value == it->value && prev_it->key < it->key);
                if (!correct_order)
                {
                    is_sorted = false;
                    printf("Complex sort error: (%zu,%s,%d) vs (%zu,%s,%d)\n", prev_it->value.length(), prev_it->value.c_str(), prev_it->key, it->value.length(), it->value.c_str(), it->key);
                    break;
                }
            }
            prev_it = it;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Complex comparator test passed\n");
    }

    // 测试7：排序后再插入新元素
    printf("Test 7: Insert after sorting\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入并排序
        for (int i = 10; i >= 1; --i)
        {
            TestPairWithList pair(i * 2, "value" + std::to_string(i * 2));
            ht.insert_unique(pair);
        }

        ht.SortListInsert();

        // 排序后插入新元素
        TestPairWithList new_pair1(5, "value5");
        TestPairWithList new_pair2(25, "value25");
        ht.insert_unique(new_pair1);
        ht.insert_unique(new_pair2);

        // 再次排序
        ht.SortListInsert();

        // 验证结果
        std::vector<int> expected = {2, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 25};
        size_t i = 0;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it, ++i)
        {
            EXPECT_EQ(it->key, expected[i]);
        }

        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Insert after sorting test passed\n");
    }

    printf("========== Sort Edge Cases and Stress Test Completed ==========\n");
}

/**
 * @brief 真正的大数据量排序测试
 * @note 使用大容量哈希表测试更大规模的数据集
 */
TEST(NFShmHashTableWithListTest, VeryLargeDataSortTest)
{
    printf("========== Very Large Data Sort Test ==========\n");

    // 测试1：500个元素测试
    printf("Test 1: 500 elements sorting\n");
    {
        LargeTestHashTableWithList ht;
        ht.CreateInit();

        const int LARGE_SIZE = 500;
        std::vector<int> reverse_keys;

        // 生成倒序序列（最坏情况）
        for (int i = LARGE_SIZE; i > 0; --i)
        {
            reverse_keys.push_back(i);
        }

        // 插入数据
        for (int key : reverse_keys)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Inserted %zu elements (reverse order)\n", ht.size());
        EXPECT_EQ(ht.size(), LARGE_SIZE);

        // 排序并计时
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("500 elements sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int expected_key = 1;
        bool is_sorted = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key != expected_key)
            {
                is_sorted = false;
                printf("Sort error: expected %d, got %d\n", expected_key, it->key);
                break;
            }
            expected_key++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(expected_key - 1, LARGE_SIZE);
        EXPECT_TRUE(ht.ValidateListIntegrity());

        // 验证哈希表功能仍然正常
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            auto found = ht.find(it->key);
            EXPECT_NE(found, ht.end());
            EXPECT_EQ(found->key, it->key);
        }

        printf("500 elements test passed!\n");
    }

    // 测试2：1000个元素测试
    printf("\nTest 2: 1000 elements sorting\n");
    {
        LargeTestHashTableWithList ht;
        ht.CreateInit();

        const int MAX_SIZE = 1000;
        std::vector<int> shuffle_keys;

        // 生成洗牌序列
        for (int i = 1; i <= MAX_SIZE; ++i)
        {
            shuffle_keys.push_back(i);
        }
        std::random_shuffle(shuffle_keys.begin(), shuffle_keys.end());

        // 插入数据
        for (int key : shuffle_keys)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Inserted %zu elements (shuffled order)\n", ht.size());
        EXPECT_EQ(ht.size(), MAX_SIZE);

        // 排序并计时
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListInsert();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        printf("1000 elements sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int expected_key = 1;
        bool is_sorted = true;
        size_t count = 0;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key != expected_key)
            {
                is_sorted = false;
                printf("Sort error at position %zu: expected %d, got %d\n", count, expected_key, it->key);
                break;
            }
            expected_key++;
            count++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(expected_key - 1, MAX_SIZE);
        EXPECT_TRUE(ht.ValidateListIntegrity());

        printf("1000 elements test passed!\n");
    }

    // 测试3：性能对比（不同规模的O(n平方)复杂度验证）
    printf("\nTest 3: Performance scaling verification\n");
    {
        std::vector<int> sizes = {100, 200, 400, 800};
        std::vector<long long> times;

        for (int size : sizes)
        {
            LargeTestHashTableWithList ht;
            ht.CreateInit();

            // 生成最坏情况数据（倒序）
            for (int i = size; i > 0; --i)
            {
                TestPairWithList pair(i, "value" + std::to_string(i));
                ht.insert_unique(pair);
            }

            // 排序并计时
            auto start = std::chrono::high_resolution_clock::now();
            ht.SortListInsert();
            auto end = std::chrono::high_resolution_clock::now();
            auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
            times.push_back(duration.count());

            printf("Size %d: %lld microseconds\n", size, duration.count());

            // 快速验证结果正确性
            int expected = 1;
            bool correct = true;
            for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
            {
                if (it->key != expected)
                {
                    correct = false;
                    break;
                }
                expected++;
            }
            EXPECT_TRUE(correct);
            EXPECT_TRUE(ht.ValidateListIntegrity());
        }

        // 分析性能比率（应该大致符合O(n平方)）
        printf("\nPerformance analysis:\n");
        for (size_t i = 1; i < sizes.size(); ++i)
        {
            double size_ratio = (double)sizes[i] / sizes[i - 1];
            double time_ratio = (double)times[i] / times[i - 1];
            printf("Size ratio %.1fx -> Time ratio %.1fx\n", size_ratio, time_ratio);

            // 对于O(n平方)算法，时间比应该接近size_ratio²
            double expected_time_ratio = size_ratio * size_ratio;
            if (time_ratio > 0.5 * expected_time_ratio && time_ratio < 3.0 * expected_time_ratio)
            {
                printf("Time complexity appears to be O(n平方) as expected\n");
            }
        }
    }

    printf("========== Very Large Data Sort Test Completed ==========\n");
}

// ==================== 性能对比测试辅助函数 ====================

/**
 * @brief 生成测试数据
 * @param size 数据大小
 * @param pattern 数据模式：0=随机，1=倒序，2=已排序，3=部分排序
 * @return 生成的数据向量
 */
std::vector<int> GenerateTestData(int size, int pattern)
{
    std::vector<int> data;
    data.reserve(size);

    switch (pattern)
    {
        case 0: // 随机数据
        {
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<> dis(1, size * 10);
            for (int i = 0; i < size; ++i)
            {
                data.push_back(dis(gen));
            }
            break;
        }
        case 1: // 倒序数据（最坏情况）
        {
            for (int i = size; i > 0; --i)
            {
                data.push_back(i);
            }
            break;
        }
        case 2: // 已排序数据（最佳情况）
        {
            for (int i = 1; i <= size; ++i)
            {
                data.push_back(i);
            }
            break;
        }
        case 3: // 部分排序数据
        {
            for (int i = 1; i <= size; ++i)
            {
                data.push_back(i);
            }
            // 打乱后半部分
            std::random_device rd;
            std::mt19937 gen(rd());
            std::shuffle(data.begin() + size / 2, data.end(), gen);
            break;
        }
    }

    return data;
}

/**
 * @brief SortListQuick功能测试
 * @note 测试SortListQuick的基本功能和各种场景
 */
TEST(NFShmHashTableWithListTest, SortListQuickFunctionalityTest)
{
    printf("========== SortListQuick Functionality Test ==========\n");

    // 测试1：基本排序功能
    printf("Test 1: Basic SortListQuick functionality\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入乱序数据
        std::vector<int> test_data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Before SortListQuick: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
        }
        printf("\n");

        // 使用SortListQuick排序
        ht.SortListQuick();

        printf("After SortListQuick: ");
        std::vector<int> sorted_result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
            sorted_result.push_back(it->key);
        }
        printf("\n");

        // 验证排序结果
        std::vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        EXPECT_EQ(sorted_result, expected);
        EXPECT_EQ(ht.size(), test_data.size());
        EXPECT_TRUE(ht.ValidateListIntegrity());

        // 验证哈希表功能仍然正常
        for (int key : test_data)
        {
            auto found = ht.find(key);
            EXPECT_NE(found, ht.end());
            EXPECT_EQ(found->key, key);
        }

        printf("Basic SortListQuick test passed\n");
    }

    // 测试2：自定义比较器（降序）
    printf("\nTest 2: SortListQuick with custom comparator (descending)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据
        for (int i = 1; i <= 10; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        // 使用降序比较器
        ht.SortListQuick(std::greater<TestPairWithList>());

        // 验证降序排列
        int prev_key = 11;
        bool is_descending = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key >= prev_key)
            {
                is_descending = false;
                break;
            }
            prev_key = it->key;
        }

        EXPECT_TRUE(is_descending);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Descending sort test passed\n");
    }

    // 测试3：lambda表达式比较器
    printf("\nTest 3: SortListQuick with lambda comparator\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据：偶数和奇数
        std::vector<int> mixed_data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        for (int key : mixed_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        // 使用lambda：偶数在前，奇数在后，同类内部升序
        ht.SortListQuick([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if ((a.key % 2) != (b.key % 2))
            {
                return (a.key % 2) == 0; // 偶数返回true（排在前面）
            }
            return a.key < b.key; // 同奇偶性时按升序
        });

        // 验证结果：应该是偶数{2,4,6,8,10}在前，奇数{1,3,5,7,9}在后
        std::vector<int> result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            result.push_back(it->key);
        }

        std::vector<int> expected = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
        EXPECT_EQ(result, expected);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Lambda comparator test passed\n");
    }

    // 测试4：边界情况 - 空表
    printf("\nTest 4: SortListQuick on empty table\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 对空表排序
        ht.SortListQuick();

        EXPECT_EQ(ht.size(), 0);
        EXPECT_TRUE(ht.empty());
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Empty table test passed\n");
    }

    // 测试5：边界情况 - 单元素
    printf("\nTest 5: SortListQuick on single element\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        TestPairWithList pair(42, "single");
        ht.insert_unique(pair);

        ht.SortListQuick();

        EXPECT_EQ(ht.size(), 1);
        auto it = ht.list_begin();
        EXPECT_EQ(it->key, 42);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Single element test passed\n");
    }

    // 测试6：边界情况 - 已排序数据
    printf("\nTest 6: SortListQuick on already sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入已排序数据
        for (int i = 1; i <= 20; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        ht.SortListQuick();

        // 验证仍然有序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 20);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Already sorted data test passed\n");
    }

    // 测试7：边界情况 - 倒序数据
    printf("\nTest 7: SortListQuick on reverse sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入倒序数据
        for (int i = 30; i >= 1; --i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        ht.SortListQuick();

        // 验证正序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 30);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Reverse sorted data test passed\n");
    }

    printf("========== SortListQuick Functionality Test Completed ==========\n");
}

/**
 * @brief SortListMerge功能测试
 * @note 测试SortListMerge（链表归并排序）的基本功能和各种场景
 */
TEST(NFShmHashTableWithListTest, SortListMergeFunctionalityTest)
{
    printf("========== SortListMerge Functionality Test ==========\n");

    // 测试1：基本排序功能
    printf("Test 1: Basic SortListMerge functionality\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入乱序数据
        std::vector<int> test_data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Before SortListMerge: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
        }
        printf("\n");

        // 使用SortListMerge排序
        ht.SortListMerge();

        printf("After SortListMerge: ");
        std::vector<int> sorted_result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
            sorted_result.push_back(it->key);
        }
        printf("\n");

        // 验证排序结果
        std::vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        EXPECT_EQ(sorted_result, expected);
        EXPECT_EQ(ht.size(), test_data.size());
        EXPECT_TRUE(ht.ValidateListIntegrity());

        // 验证哈希表功能仍然正常
        for (int key : test_data)
        {
            auto found = ht.find(key);
            EXPECT_NE(found, ht.end());
            EXPECT_EQ(found->key, key);
        }

        printf("Basic SortListMerge test passed\n");
    }

    // 测试2：自定义比较器（降序）
    printf("\nTest 2: SortListMerge with custom comparator (descending)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据
        for (int i = 1; i <= 10; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        // 使用降序比较器
        ht.SortListMerge(std::greater<TestPairWithList>());

        // 验证降序排列
        int prev_key = 11;
        bool is_descending = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key >= prev_key)
            {
                is_descending = false;
                break;
            }
            prev_key = it->key;
        }

        EXPECT_TRUE(is_descending);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Descending sort test passed\n");
    }

    // 测试3：lambda表达式比较器
    printf("\nTest 3: SortListMerge with lambda comparator\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据：偶数和奇数
        std::vector<int> mixed_data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        for (int key : mixed_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        // 使用lambda：偶数在前，奇数在后，同类内部升序
        ht.SortListMerge([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if ((a.key % 2) != (b.key % 2))
            {
                return (a.key % 2) == 0; // 偶数返回true（排在前面）
            }
            return a.key < b.key; // 同奇偶性时按升序
        });

        // 验证结果：应该是偶数{2,4,6,8,10}在前，奇数{1,3,5,7,9}在后
        std::vector<int> result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            result.push_back(it->key);
        }

        std::vector<int> expected = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
        EXPECT_EQ(result, expected);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Lambda comparator test passed\n");
    }

    // 测试4：边界情况 - 空表
    printf("\nTest 4: SortListMerge on empty table\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 对空表排序
        ht.SortListMerge();

        EXPECT_EQ(ht.size(), 0);
        EXPECT_TRUE(ht.empty());
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Empty table test passed\n");
    }

    // 测试5：边界情况 - 单元素
    printf("\nTest 5: SortListMerge on single element\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        TestPairWithList pair(42, "single");
        ht.insert_unique(pair);

        ht.SortListMerge();

        EXPECT_EQ(ht.size(), 1);
        auto it = ht.list_begin();
        EXPECT_EQ(it->key, 42);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Single element test passed\n");
    }

    // 测试6：边界情况 - 已排序数据
    printf("\nTest 6: SortListMerge on already sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入已排序数据
        for (int i = 1; i <= 20; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        ht.SortListMerge();

        // 验证仍然有序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 20);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Already sorted data test passed\n");
    }

    // 测试7：边界情况 - 倒序数据
    printf("\nTest 7: SortListMerge on reverse sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入倒序数据
        for (int i = 30; i >= 1; --i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        ht.SortListMerge();

        // 验证正序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 30);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Reverse sorted data test passed\n");
    }

    // 测试8：大数据集测试
    printf("\nTest 8: Large data set (50 elements)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入50个随机数据
        std::vector<int> large_data;
        for (int i = 1; i <= 50; ++i)
        {
            large_data.push_back(i);
        }
        std::random_shuffle(large_data.begin(), large_data.end());

        for (int key : large_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Before sort: 50 shuffled elements\n");

        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListMerge();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("Sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int expected_key = 1;
        bool is_sorted = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key != expected_key)
            {
                is_sorted = false;
                break;
            }
            expected_key++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(ht.size(), 50);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Large data set test passed\n");
    }

    printf("========== SortListMerge Functionality Test Completed ==========\n");
}

/**
 * @brief SortListSelect功能测试
 * @note 测试SortListSelect（链表选择排序）的基本功能和各种场景
 */
TEST(NFShmHashTableWithListTest, SortListSelectFunctionalityTest)
{
    printf("========== SortListSelect Functionality Test ==========\n");

    // 测试1：基本排序功能
    printf("Test 1: Basic SortListSelect functionality\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入乱序数据
        std::vector<int> test_data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Before SortListSelect: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
        }
        printf("\n");

        // 使用SortListSelect排序
        ht.SortListSelect();

        printf("After SortListSelect: ");
        std::vector<int> sorted_result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("%d ", it->key);
            sorted_result.push_back(it->key);
        }
        printf("\n");

        // 验证排序结果
        std::vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        EXPECT_EQ(sorted_result, expected);
        EXPECT_EQ(ht.size(), test_data.size());
        EXPECT_TRUE(ht.ValidateListIntegrity());

        // 验证哈希表功能仍然正常
        for (int key : test_data)
        {
            auto found = ht.find(key);
            EXPECT_NE(found, ht.end());
            EXPECT_EQ(found->key, key);
        }

        printf("Basic SortListSelect test passed\n");
    }

    // 测试2：自定义比较器（降序）
    printf("\nTest 2: SortListSelect with custom comparator (descending)\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据
        for (int i = 1; i <= 10; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        // 使用降序比较器
        ht.SortListSelect(std::greater<TestPairWithList>());

        // 验证降序排列
        int prev_key = 11;
        bool is_descending = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key >= prev_key)
            {
                is_descending = false;
                break;
            }
            prev_key = it->key;
        }

        EXPECT_TRUE(is_descending);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Descending sort test passed\n");
    }

    // 测试3：lambda表达式比较器
    printf("\nTest 3: SortListSelect with lambda comparator\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入数据：偶数和奇数
        std::vector<int> mixed_data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        for (int key : mixed_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        // 使用lambda：偶数在前，奇数在后，同类内部升序
        ht.SortListSelect([](const TestPairWithList& a, const TestPairWithList& b)
        {
            if ((a.key % 2) != (b.key % 2))
            {
                return (a.key % 2) == 0; // 偶数返回true（排在前面）
            }
            return a.key < b.key; // 同奇偶性时按升序
        });

        // 验证结果：应该是偶数在前，奇数在后
        std::vector<int> result;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            result.push_back(it->key);
        }

        // 检查偶数都在奇数前面
        bool even_before_odd = true;
        bool found_odd = false;
        for (int val : result)
        {
            if (val % 2 == 1)
            {
                found_odd = true;
            }
            else if (found_odd)
            {
                even_before_odd = false;
                break;
            }
        }

        EXPECT_TRUE(even_before_odd);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Lambda comparator test passed\n");
    }

    // 测试4：边界情况 - 空表
    printf("\nTest 4: SortListSelect on empty table\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 对空表排序
        ht.SortListSelect();

        EXPECT_EQ(ht.size(), 0);
        EXPECT_TRUE(ht.empty());
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Empty table test passed\n");
    }

    // 测试5：边界情况 - 单元素
    printf("\nTest 5: SortListSelect on single element\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        TestPairWithList pair(42, "single");
        ht.insert_unique(pair);

        ht.SortListSelect();

        EXPECT_EQ(ht.size(), 1);
        auto it = ht.list_begin();
        EXPECT_EQ(it->key, 42);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Single element test passed\n");
    }

    // 测试6：边界情况 - 已排序数据
    printf("\nTest 6: SortListSelect on already sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入已排序数据（选择排序性能稳定）
        for (int i = 1; i <= 20; ++i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        printf("Testing selection sort on already sorted data...\n");
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListSelect();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("Already sorted data sort completed in %lld microseconds\n", duration.count());

        // 验证仍然有序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 20);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Already sorted data test passed\n");
    }

    // 测试7：边界情况 - 倒序数据
    printf("\nTest 7: SortListSelect on reverse sorted data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入倒序数据（选择排序性能稳定）
        for (int i = 30; i >= 1; --i)
        {
            TestPairWithList pair(i, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        printf("Testing selection sort on reverse sorted data...\n");
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListSelect();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("Reverse sorted data sort completed in %lld microseconds\n", duration.count());

        // 验证正序
        int expected_key = 1;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            EXPECT_EQ(it->key, expected_key);
            expected_key++;
        }

        EXPECT_EQ(ht.size(), 30);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Reverse sorted data test passed\n");
    }

    // 测试8：随机数据
    printf("\nTest 8: SortListSelect on random data\n");
    {
        TestHashTableWithList ht;
        ht.CreateInit();

        // 插入50个随机数据（选择排序性能稳定）
        std::vector<int> random_data;
        for (int i = 1; i <= 50; ++i)
        {
            random_data.push_back(i);
        }
        std::random_shuffle(random_data.begin(), random_data.end());

        for (int key : random_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        printf("Testing selection sort on random data...\n");
        auto start = std::chrono::high_resolution_clock::now();
        ht.SortListSelect();
        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

        printf("Random data sort completed in %lld microseconds\n", duration.count());

        // 验证排序结果
        int expected_key = 1;
        bool is_sorted = true;
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            if (it->key != expected_key)
            {
                is_sorted = false;
                break;
            }
            expected_key++;
        }

        EXPECT_TRUE(is_sorted);
        EXPECT_EQ(ht.size(), 50);
        EXPECT_TRUE(ht.ValidateListIntegrity());
        printf("Random data test passed\n");
    }

    printf("========== SortListSelect Functionality Test Completed ==========\n");
}

/**
 * @brief 五种排序算法全面性能对比测试
 * @note 对比SortListInsert、SortListQuick、SortListMerge、SortListMergeFast、SortListSelect的综合性能
 * @note 包含哈希表完整性验证，确保排序后哈希访问功能正常
 */
TEST(NFShmHashTableWithListTest, ComprehensiveSortPerformanceTest)
{
    printf("========== Comprehensive Sort Performance Comparison ==========\n");

    const std::vector<int> test_sizes = {10, 20, 30, 40, 50};
    const std::vector<std::string> pattern_names = {"随机数据", "倒序数据", "已排序数据", "部分排序"};

    printf("五种排序算法性能对比（微秒）\n");
    printf("%-8s %-12s %-15s %-15s %-15s %-18s %-15s %-20s %-20s\n", "规模", "数据模式", "SortListInsert(插入)", "SortListQuick(快速)", "SortListMerge(归并)", "SortListMergeFast(优化)", "SortListSelect(选择)", "最快算法", "性能优势");
    printf("%-8s %-12s %-15s %-15s %-15s %-18s %-15s %-20s %-20s\n", "----", "--------", "-------------", "-------------", "-------------", "----------------", "-------------", "--------", "--------");

    for (int size : test_sizes)
    {
        for (int pattern = 0; pattern < 4; ++pattern)
        {
            // 生成测试数据
            std::vector<int> original_data = GenerateTestData(size, pattern);

            long long sortlist_time = 0, sortlist2_time = 0, sortlist3_time = 0, sortlistfast_time = 0, sortlist4_time = 0;

            // 测试SortList（插入排序）
            {
                TestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListInsert();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证结果正确性
                int prev_key = 0;
                bool is_sorted = true;
                for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
                {
                    if (it->key < prev_key)
                    {
                        is_sorted = false;
                        break;
                    }
                    prev_key = it->key;
                }
                EXPECT_TRUE(is_sorted);

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListInsert排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListQuick（快速排序）
            {
                TestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListQuick();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist2_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证结果正确性
                int prev_key = 0;
                bool is_sorted = true;
                for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
                {
                    if (it->key < prev_key)
                    {
                        is_sorted = false;
                        break;
                    }
                    prev_key = it->key;
                }
                EXPECT_TRUE(is_sorted);

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListQuick排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListMerge（归并排序）
            {
                TestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListMerge();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist3_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证结果正确性
                int prev_key = 0;
                bool is_sorted = true;
                for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
                {
                    if (it->key < prev_key)
                    {
                        is_sorted = false;
                        break;
                    }
                    prev_key = it->key;
                }
                EXPECT_TRUE(is_sorted);

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListMergeFast（高性能归并排序）
            {
                TestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListMergeFast();
                auto end = std::chrono::high_resolution_clock::now();
                sortlistfast_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证结果正确性
                int prev_key = 0;
                bool is_sorted = true;
                for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
                {
                    if (it->key < prev_key)
                    {
                        is_sorted = false;
                        break;
                    }
                    prev_key = it->key;
                }
                EXPECT_TRUE(is_sorted);

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListMergeFast排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListSelect（选择排序）
            {
                TestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListSelect();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist4_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证结果正确性
                int prev_key = 0;
                bool is_sorted = true;
                for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
                {
                    if (it->key < prev_key)
                    {
                        is_sorted = false;
                        break;
                    }
                    prev_key = it->key;
                }
                EXPECT_TRUE(is_sorted);

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListSelect排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 分析最快算法和性能优势
            long long min_time = std::min({sortlist_time, sortlist2_time, sortlist3_time, sortlistfast_time, sortlist4_time});
            std::string fastest_algo;
            double advantage = 1.0;

            if (min_time == sortlist_time)
            {
                fastest_algo = "SortListInsert";
                advantage = std::max({(double)sortlist2_time / sortlist_time, (double)sortlist3_time / sortlist_time, (double)sortlistfast_time / sortlist_time, (double)sortlist4_time / sortlist_time});
            }
            else if (min_time == sortlist2_time)
            {
                fastest_algo = "SortListQuick";
                advantage = std::max({(double)sortlist_time / sortlist2_time, (double)sortlist3_time / sortlist2_time, (double)sortlistfast_time / sortlist2_time, (double)sortlist4_time / sortlist2_time});
            }
            else if (min_time == sortlist3_time)
            {
                fastest_algo = "SortListMerge";
                advantage = std::max({(double)sortlist_time / sortlist3_time, (double)sortlist2_time / sortlist3_time, (double)sortlistfast_time / sortlist3_time, (double)sortlist4_time / sortlist3_time});
            }
            else if (min_time == sortlistfast_time)
            {
                fastest_algo = "SortListMergeFast";
                advantage = std::max({(double)sortlist_time / sortlistfast_time, (double)sortlist2_time / sortlistfast_time, (double)sortlist3_time / sortlistfast_time, (double)sortlist4_time / sortlistfast_time});
            }
            else
            {
                fastest_algo = "SortListSelect";
                advantage = std::max({(double)sortlist_time / sortlist4_time, (double)sortlist2_time / sortlist4_time, (double)sortlist3_time / sortlist4_time, (double)sortlistfast_time / sortlist4_time});
            }

            printf("%-8d %-12s %-15lld %-15lld %-15lld %-18lld %-15lld %-20s %-20.2fx\n", size, pattern_names[pattern].c_str(), sortlist_time, sortlist2_time, sortlist3_time, sortlistfast_time, sortlist4_time, fastest_algo.c_str(), advantage);
        }
        printf("\n");
    }

    printf("\n========== 大数据集性能对比（使用LargeTestHashTableWithList）==========\n");

    const std::vector<int> large_sizes = {100, 200, 500, 1000};

    printf("%-8s %-12s %-15s %-15s %-15s %-18s %-15s %-20s %-20s\n", "规模", "数据模式", "SortListInsert(插入)", "SortListQuick(快速)", "SortListMerge(归并)", "SortListMergeFast(优化)", "SortListSelect(选择)", "最快算法", "性能优势");
    printf("%-8s %-12s %-15s %-15s %-15s %-18s %-15s %-20s %-20s\n", "----", "--------", "-------------", "-------------", "-------------", "----------------", "-------------", "--------", "--------");

    for (int size : large_sizes)
    {
        for (int pattern = 0; pattern < 4; ++pattern)
        {
            // 生成测试数据
            std::vector<int> original_data = GenerateTestData(size, pattern);

            long long sortlist_time = 0, sortlist2_time = 0, sortlist3_time = 0, sortlistfast_time = 0, sortlist4_time = 0;

            // 测试SortList（插入排序）
            {
                LargeTestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListInsert();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListInsert排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListQuick（快速排序）
            {
                LargeTestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListQuick();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist2_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListQuick排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListMerge（归并排序）
            {
                LargeTestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListMerge();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist3_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListMerge排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListMergeFast（优化归并排序）
            {
                LargeTestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListMergeFast();
                auto end = std::chrono::high_resolution_clock::now();
                sortlistfast_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListMergeFast排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 测试SortListSelect（选择排序）
            {
                LargeTestHashTableWithList ht;
                ht.CreateInit();

                for (int value : original_data)
                {
                    TestPairWithList pair(value, "value" + std::to_string(value));
                    ht.insert_unique(pair);
                }

                auto start = std::chrono::high_resolution_clock::now();
                ht.SortListSelect();
                auto end = std::chrono::high_resolution_clock::now();
                sortlist4_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                for (int value : original_data)
                {
                    auto find_it = ht.find(value);
                    EXPECT_NE(find_it, ht.end()) << "SortListSelect排序后元素 " << value << " 应能通过hash找到";
                }
            }

            // 分析最快算法和性能优势
            long long min_time = std::min({sortlist_time, sortlist2_time, sortlist3_time, sortlistfast_time, sortlist4_time});
            std::string fastest_algo;
            double advantage = 1.0;

            if (min_time == sortlist_time)
            {
                fastest_algo = "SortListInsert";
                advantage = std::max({(double)sortlist2_time / sortlist_time, (double)sortlist3_time / sortlist_time, (double)sortlistfast_time / sortlist_time, (double)sortlist4_time / sortlist_time});
            }
            else if (min_time == sortlist2_time)
            {
                fastest_algo = "SortListQuick";
                advantage = std::max({(double)sortlist_time / sortlist2_time, (double)sortlist3_time / sortlist2_time, (double)sortlistfast_time / sortlist2_time, (double)sortlist4_time / sortlist2_time});
            }
            else if (min_time == sortlist3_time)
            {
                fastest_algo = "SortListMerge";
                advantage = std::max({(double)sortlist_time / sortlist3_time, (double)sortlist2_time / sortlist3_time, (double)sortlistfast_time / sortlist3_time, (double)sortlist4_time / sortlist3_time});
            }
            else if (min_time == sortlistfast_time)
            {
                fastest_algo = "SortListMergeFast";
                advantage = std::max({(double)sortlist_time / sortlistfast_time, (double)sortlist2_time / sortlistfast_time, (double)sortlist3_time / sortlistfast_time, (double)sortlist4_time / sortlistfast_time});
            }
            else
            {
                fastest_algo = "SortListSelect";
                advantage = std::max({(double)sortlist_time / sortlist4_time, (double)sortlist2_time / sortlist4_time, (double)sortlist3_time / sortlist4_time, (double)sortlistfast_time / sortlist4_time});
            }

            printf("%-8d %-12s %-15lld %-15lld %-15lld %-18lld %-15lld %-20s %-20.2fx\n", size, pattern_names[pattern].c_str(), sortlist_time, sortlist2_time, sortlist3_time, sortlistfast_time, sortlist4_time, fastest_algo.c_str(), advantage);
        }
        printf("\n");
    }

    printf("\n========== 算法特性总结 ==========\n");
    printf("1. SortList (插入排序):\n");
    printf("   - 时间复杂度: O(n平方)，空间复杂度: O(1)\n");
    printf("   - 优势: 小数据集、已排序数据、内存极其有限场景\n");
    printf("   - 劣势: 大数据集性能急剧下降\n");
    printf("   - 最佳场景: 数据量<20且已基本有序\n");
    printf("\n2. SortListQuick (vector+std::sort):\n");
    printf("   - 时间复杂度: O(n log n)，空间复杂度: O(n)\n");
    printf("   - 优势: 利用高度优化的std::sort，性能稳定\n");
    printf("   - 劣势: 需要额外内存，重建哈希表开销\n");
    printf("   - 最佳场景: 内存充足，追求极致性能\n");
    printf("\n3. SortListMerge (链表归并排序):\n");
    printf("   - 时间复杂度: O(n log n)，空间复杂度: O(log n)\n");
    printf("   - 优势: 实现简单可靠，保持哈希表完整性\n");
    printf("   - 劣势: 递归调用，栈空间开销\n");
    printf("   - 最佳场景: 中大型数据集，平衡性能与实现复杂度\n");
    printf("\n4. SortListSelect (链表选择排序):\n");
    printf("   - 时间复杂度: O(n平方)，空间复杂度: O(n)\n");
    printf("   - 优势: 保持哈希表完整性，性能稳定可预测\n");
    printf("   - 劣势: 时间复杂度高，需要额外内存存储索引\n");
    printf("   - 最佳场景: 小数据集且需要稳定性能的场景\n");
    printf("\n========== 推荐使用策略 ==========\n");
    printf(" 数据量 ≤ 10: 使用SortList（插入排序）\n");
    printf(" 数据量 10-50: SortList vs SortListSelect，根据内存偏好选择\n");
    printf(" 数据量 50-100: 根据内存情况选择SortListQuick或SortListMerge\n");
    printf(" 数据量 > 100: 优先SortListMerge，内存充足时可选SortListQuick\n");
    printf(" 已排序数据: SortList性能最佳（接近O(n)）\n");
    printf(" 倒序数据: SortListQuick或SortListMerge，避免SortList和SortListSelect\n");
    printf(" 内存极限: 使用SortList（O(1)空间）\n");
    printf(" 内存受限: 使用SortListMerge（O(log n)空间）\n");
    printf(" 稳定性能: 使用SortListSelect（O(n平方)但可预测）\n");
    printf(" 追求极致性能: 使用SortListQuick\n");

    printf("========== Comprehensive Sort Performance Test Completed ==========\n");
}

/**
 * @brief 终极全方位排序算法性能对比测试
 * @note 对比所有排序算法：SortListInsert、SortListQuick、SortListMerge、SortListMergeFast、SortListSelect、std::vector、std::list、C数组、std::map、std::sort
 * @note 包含哈希表完整性验证，确保排序后哈希访问功能正常
 */
TEST(NFShmHashTableWithListTest, UltimateAllSortingAlgorithmsComparisonTest)
{
    printf("========== Ultimate All Sorting Algorithms Comparison Test ==========\n");

    const std::vector<int> test_sizes = {10, 50, 100, 500, 1000, 2000, 5000, 10000};
    const std::vector<std::string> pattern_names = {"随机数据", "倒序数据", "已排序数据", "部分排序"};

    printf("测试说明：\n");
    printf(" 数据规模：从10到10000元素，展现不同算法的规模化性能\n");
    printf(" SortListInsert/4（O(n平方)算法）：在大数据集上运行时间较长，请耐心等待\n");
    printf(" SortListQuick/3（O(n log n)算法）：展现对数级时间复杂度的性能优势\n");
    printf(" SortListMergeFast（优化归并）：对比标准归并与高性能优化版本\n");
    printf(" 标准库算法：提供性能基准对比\n");
    printf("\n所有排序算法终极对比（微秒）\n");
    printf("%-6s %-8s %-14s %-13s %-13s %-15s %-14s %-12s %-12s %-8s %-12s %-12s\n", "规模", "数据模式", "SortListInsert", "SortListQuick", "SortListMerge", "SortListMergeFast", "SortListSelect", "std::vector", "std::list", "C数组", "std::map", "std::sort");
    printf("%-6s %-8s %-14s %-13s %-13s %-15s %-14s %-12s %-12s %-8s %-12s %-12s\n", "----", "------", "------------", "-----------", "-----------", "-------------", "------------", "----------", "----------", "------", "----------", "---------");

    for (int size : test_sizes)
    {
        for (int pattern = 0; pattern < 4; ++pattern)
        {
            // 生成测试数据
            std::vector<int> original_data = GenerateTestData(size, pattern);

            long long sortlist1_time = 0, sortlist2_time = 0, sortlist3_time = 0, sortlistfast_time = 0, sortlist4_time = 0;
            long long vector_time = 0, list_time = 0, array_time = 0, map_time = 0, std_sort_time = 0;

            // 测试1：SortListInsert（插入排序）
            {
                if (size <= 50)
                {
                    TestHashTableWithList ht;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListInsert();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist1_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                }
                else
                {
                    MaxLargeTestHashTableWithList* maxHt = new MaxLargeTestHashTableWithList();
                    MaxLargeTestHashTableWithList& ht = *maxHt;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListInsert();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist1_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                    delete maxHt;
                }
            }

            // 测试2：SortListQuick（vector + std::sort）- 适用于所有数据规模
            {
                if (size <= 50)
                {
                    TestHashTableWithList ht;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListQuick();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist2_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                }
                else
                {
                    MaxLargeTestHashTableWithList* maxHt = new MaxLargeTestHashTableWithList();
                    MaxLargeTestHashTableWithList& ht = *maxHt;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListQuick();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist2_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                    delete maxHt;
                }
            }

            // 测试3：SortListMerge（链表归并排序）- 适用于所有数据规模
            {
                if (size <= 50)
                {
                    TestHashTableWithList ht;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListMerge();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist3_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                }
                else
                {
                    MaxLargeTestHashTableWithList* maxHt = new MaxLargeTestHashTableWithList();
                    MaxLargeTestHashTableWithList& ht = *maxHt;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListMerge();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist3_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                    delete maxHt;
                }
            }

            // 测试3.5：SortListMergeFast（高性能归并排序）- 适用于所有数据规模
            {
                if (size <= 50)
                {
                    TestHashTableWithList ht;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListMergeFast();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlistfast_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                    // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                    for (int value : original_data)
                    {
                        auto find_it = ht.find(value);
                        EXPECT_NE(find_it, ht.end()) << "SortListMergeFast排序后元素 " << value << " 应能通过hash找到";
                    }
                }
                else
                {
                    MaxLargeTestHashTableWithList* maxHt = new MaxLargeTestHashTableWithList();
                    MaxLargeTestHashTableWithList& ht = *maxHt;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListMergeFast();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlistfast_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                    // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
                    for (int value : original_data)
                    {
                        auto find_it = ht.find(value);
                        EXPECT_NE(find_it, ht.end()) << "SortListMergeFast排序后元素 " << value << " 应能通过hash找到";
                    }
                    delete maxHt;
                }
            }

            // 测试4：SortListSelect（选择排序）
            {
                if (size <= 50)
                {
                    TestHashTableWithList ht;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListSelect();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist4_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                }
                else
                {
                    MaxLargeTestHashTableWithList* maxHt = new MaxLargeTestHashTableWithList();
                    MaxLargeTestHashTableWithList& ht = *maxHt;
                    ht.CreateInit();

                    for (int value : original_data)
                    {
                        TestPairWithList pair(value, "value" + std::to_string(value));
                        ht.insert_unique(pair);
                    }

                    auto start = std::chrono::high_resolution_clock::now();
                    ht.SortListSelect();
                    auto end = std::chrono::high_resolution_clock::now();
                    sortlist4_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
                    delete maxHt;
                }
            }

            // 测试5：std::vector + std::sort
            {
                std::vector<int> vec_data = original_data;

                auto start = std::chrono::high_resolution_clock::now();
                std::sort(vec_data.begin(), vec_data.end());
                auto end = std::chrono::high_resolution_clock::now();
                vector_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // 测试6：std::list + list.sort()
            {
                std::list<int> list_data(original_data.begin(), original_data.end());

                auto start = std::chrono::high_resolution_clock::now();
                list_data.sort(); // 使用内置的归并排序
                auto end = std::chrono::high_resolution_clock::now();
                list_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // 测试7：C数组 + std::sort
            {
                int* arr = new int[size];
                for (int i = 0; i < size; ++i)
                    arr[i] = original_data[i];

                auto start = std::chrono::high_resolution_clock::now();
                std::sort(arr, arr + size);
                auto end = std::chrono::high_resolution_clock::now();
                array_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

                delete[] arr;
            }

            // 测试8：std::map（红黑树）自动排序
            {
                auto start = std::chrono::high_resolution_clock::now();

                std::map<int, std::string> map_data;
                for (int value : original_data)
                {
                    map_data[value] = "value" + std::to_string(value);
                }

                // 遍历以确保所有操作完成
                volatile int sum = 0;
                for (const auto& pair : map_data)
                {
                    sum += pair.first;
                }

                auto end = std::chrono::high_resolution_clock::now();
                map_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // 测试9：纯std::sort作为基准参考
            {
                std::vector<int> std_data = original_data;

                auto start = std::chrono::high_resolution_clock::now();
                std::sort(std_data.begin(), std_data.end());
                auto end = std::chrono::high_resolution_clock::now();
                std_sort_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // 输出结果
            printf("%-6d %-8s %-14lld %-13lld %-13lld %-15lld %-14lld %-12lld %-12lld %-8lld %-12lld %-12lld\n", size, pattern_names[pattern].c_str(), sortlist1_time, sortlist2_time, sortlist3_time, sortlistfast_time, sortlist4_time, vector_time, list_time, array_time, map_time, std_sort_time);
        }
        printf("\n");
    }

    printf("\n========== 算法特性全面对比分析 ==========\n");
    printf("1. SortListInsert (插入排序):\n");
    printf("   - 时间: O(n平方), 空间: O(1), 稳定:\n");
    printf("   - 适用: 小数据集、已排序数据\n");
    printf("   - 特点: 简单实现，适应性好\n");

    printf("\n2. SortListQuick (vector+std::sort):\n");
    printf("   - 时间: O(n log n), 空间: O(n), 稳定:\n");
    printf("   - 适用: 追求极致性能，内存充足\n");
    printf("   - 特点: 重建哈希表，利用高度优化的std::sort\n");

    printf("\n3. SortListMerge (链表归并排序):\n");
    printf("   - 时间: O(n log n), 空间: O(log n), 稳定:\n");
    printf("   - 适用: 中大型数据集，平衡性能与复杂度\n");
    printf("   - 特点: 保持哈希表完整性，实现简单可靠\n");

    printf("\n4. SortListSelect (链表选择排序):\n");
    printf("   - 时间: O(n平方), 空间: O(n), 稳定:\n");
    printf("   - 适用: 小数据集，需保持哈希表完整性\n");
    printf("   - 特点: 保持哈希完整性，实现简单，性能稳定\n");

    printf("\n5. std::vector + std::sort:\n");
    printf("   - 时间: O(n log n), 空间: O(log n), 稳定:\n");
    printf("   - 适用: 纯排序需求，高性能\n");
    printf("   - 特点: 内存连续，缓存友好，高度优化\n");

    printf("\n6. std::list::sort:\n");
    printf("   - 时间: O(n log n), 空间: O(log n), 稳定:\n");
    printf("   - 适用: 链表数据结构\n");
    printf("   - 特点: 归并排序实现，稳定但性能一般\n");

    printf("\n7. C数组 + std::sort:\n");
    printf("   - 时间: O(n log n), 空间: O(log n), 稳定:\n");
    printf("   - 适用: 原生数组，最小开销\n");
    printf("   - 特点: 最快的纯排序，无容器开销\n");

    printf("\n8. std::map (红黑树):\n");
    printf("   - 时间: O(n log n), 空间: O(n), 稳定:\n");
    printf("   - 适用: 需要有序映射\n");
    printf("   - 特点: 插入时自动排序，查找效率O(log n)\n");

    printf("\n========== 性能排序预期 ==========\n");
    printf("最快 → 最慢（不同数据规模）：\n");
    printf("\n小数据集（≤100）：\n");
    printf("1. C数组 + std::sort（原生最快）\n");
    printf("2. std::vector + std::sort（容器最快）\n");
    printf("3. SortListQuick（利用std::sort）\n");
    printf("4. SortListMerge（稳定的O(n log n)）\n");
    printf("5. std::list::sort（链表归并）\n");
    printf("6. std::map（红黑树插入）\n");
    printf("7. SortListInsert（插入排序）\n");
    printf("8. SortListSelect（选择排序）\n");
    printf("\n中等数据集（100-1000）：\n");
    printf("1. C数组 + std::sort（原生最快）\n");
    printf("2. std::vector + std::sort（容器最快）\n");
    printf("3. SortListQuick（利用std::sort）\n");
    printf("4. SortListMerge（稳定的O(n log n)）\n");
    printf("5. std::list::sort（链表归并）\n");
    printf("6. std::map（红黑树插入）\n");
    printf("7. SortListInsert（插入排序，性能下降明显）\n");
    printf("8. SortListSelect（选择排序）\n");
    printf("\n大数据集（≥1000）：\n");
    printf("1. C数组 + std::sort（原生最快）\n");
    printf("2. std::vector + std::sort（容器最快）\n");
    printf("3. SortListQuick（利用std::sort）\n");
    printf("4. SortListMerge（稳定的O(n log n)）\n");
    printf("5. std::list::sort（链表归并）\n");
    printf("6. std::map（红黑树插入）\n");
    printf("7. SortListInsert（插入排序，性能较慢）\n");
    printf("8. SortListSelect（选择排序，性能较慢）\n");

    printf("\n========== 使用建议（按数据规模）==========\n");
    printf("\n小数据集（≤100）：\n");
    printf(" 纯排序性能：C数组 > std::vector > SortListQuick\n");
    printf(" 保持哈希表：SortListInsert ≈ SortListSelect > SortListMerge > SortListQuick\n");
    printf(" 稳定排序：SortListInsert > SortListQuick ≈ SortListMerge\n");
    printf(" 实现简单：SortListInsert ≈ SortListSelect > SortListMerge > SortListQuick\n");

    printf("\n中等数据集（100-1000）：\n");
    printf(" 纯排序性能：C数组 > std::vector > SortListQuick\n");
    printf(" 保持哈希表：SortListMerge > SortListQuick > SortListInsert（性能下降）\n");
    printf(" 稳定排序：SortListQuick ≈ SortListMerge > SortListInsert\n");
    printf(" 内存受限：SortListMerge > SortListInsert > SortListQuick\n");

    printf("\n大数据集（≥1000）：\n");
    printf(" 纯排序性能：C数组 > std::vector > SortListQuick\n");
    printf(" 保持哈希表：SortListMerge > SortListQuick > SortListInsert ≈ SortListSelect\n");
    printf(" 稳定排序：SortListQuick ≈ SortListMerge\n");
    printf(" 内存受限：SortListMerge > SortListQuick\n");

    printf("\n通用建议：\n");
    printf(" 需要查找：std::map 提供O(log n)查找\n");
    printf(" 性能稳定：SortListMerge（所有规模都是O(n log n)）\n");
    printf(" 极致性能：SortListQuick（利用高度优化的std::sort）\n");
    printf(" 学习简单：SortListInsert和SortListSelect（O(n平方)算法易懂）\n");

    printf("========== Ultimate All Sorting Algorithms Test Completed ==========\n");
}

//---
// 新增：MoveToNodeFront/MoveToNodeBack 和排序插入相关测试
//---

/**
 * @brief 测试 MoveToNodeFront 功能
 * @note 验证节点能正确移动到满足条件的第一个节点前面
 */
void TestMoveToNodeFront()
{
    printf("========== Testing MoveToNodeFront ==========\n");

    typedef NFShmHashTableWithList<TestPairWithList, int, 50, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> TestHashTable;
    TestHashTable ht;
    ht.CreateInit();

    // 插入测试数据
    std::vector<TestPairWithList> test_data = {TestPairWithList(1, "one"), TestPairWithList(3, "three"), TestPairWithList(5, "five"), TestPairWithList(7, "seven"), TestPairWithList(9, "nine")};

    for (const auto& pair : test_data)
    {
        ht.insert_unique(pair);
    }

    printf("初始链表顺序: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
    }
    printf("\n");

    // 测试1: 将key=5的节点移动到所有key>3的节点前面
    auto target_it = ht.find(5);
    if (target_it != ht.end())
    {
        std::function<bool(const TestPairWithList& self, const TestPairWithList& value)> compareFunc = [](const TestPairWithList& self, const TestPairWithList& value) -> bool
        {
            return self.key < value.key && value.key > 3; // 移动到key>3的第一个节点前面
        };

        ht.MoveToNodeFront(target_it, compareFunc);

        printf("移动key=5到key>3的节点前面后: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(%d,%s) ", it->key, it->value.c_str());
        }
        printf("\n");
    }

    // 测试2: 将key=9的节点移动到链表头部
    target_it = ht.find(9);
    if (target_it != ht.end())
    {
        std::function<bool(const TestPairWithList& self, const TestPairWithList& value)> compareFunc = [](const TestPairWithList& self, const TestPairWithList& value) -> bool
        {
            return true; // 总是返回true，移动到第一个节点前面（即头部）
        };

        ht.MoveToNodeFront(target_it, compareFunc);

        printf("移动key=9到链表头部后: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(%d,%s) ", it->key, it->value.c_str());
        }
        printf("\n");
    }

    printf("========== MoveToNodeFront Test Completed ==========\n\n");
}

/**
 * @brief 测试 MoveToNodeBack 功能
 * @note 验证节点能正确移动到满足条件的第一个节点后面
 */
void TestMoveToNodeBack()
{
    printf("========== Testing MoveToNodeBack ==========\n");

    typedef NFShmHashTableWithList<TestPairWithList, int, 50, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> TestHashTable;
    TestHashTable ht;
    ht.CreateInit();

    // 插入测试数据
    std::vector<TestPairWithList> test_data = {TestPairWithList(2, "two"), TestPairWithList(4, "four"), TestPairWithList(6, "six"), TestPairWithList(8, "eight"), TestPairWithList(10, "ten")};

    for (const auto& pair : test_data)
    {
        ht.insert_unique(pair);
    }

    printf("初始链表顺序: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
    }
    printf("\n");

    // 测试1: 将key=2的节点移动到key=6的节点后面
    auto target_it = ht.find(2);
    if (target_it != ht.end())
    {
        std::function<bool(const TestPairWithList& self, const TestPairWithList& value)> compareFunc = [](const TestPairWithList& self, const TestPairWithList& value) -> bool
        {
            return value.key == 6; // 移动到key=6的节点后面
        };

        ht.MoveToNodeBack(target_it, compareFunc);

        printf("移动key=2到key=6后面: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(%d,%s) ", it->key, it->value.c_str());
        }
        printf("\n");
    }

    // 测试2: 将key=10的节点移动到链表尾部（如果没有满足条件的节点）
    target_it = ht.find(10);
    if (target_it != ht.end())
    {
        std::function<bool(const TestPairWithList& self, const TestPairWithList& value)> compareFunc = [](const TestPairWithList& self, const TestPairWithList& value) -> bool
        {
            return value.key > 100; // 永远不满足，应该移动到尾部
        };

        ht.MoveToNodeBack(target_it, compareFunc);

        printf("移动key=10到尾部（无满足条件节点）: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(%d,%s) ", it->key, it->value.c_str());
        }
        printf("\n");
    }

    printf("========== MoveToNodeBack Test Completed ==========\n\n");
}

// ==================== insert_list_sorted_unique 和 insert_list_sorted_equal 测试 ====================

/**
 * @brief 测试 insert_list_sorted_unique 基本功能
 * @note 验证排序插入唯一元素的基本功能
 */
TEST(NFShmHashTableWithListTest, InsertSortedUniqueBasic)
{
    printf("========== Insert Sorted Unique Basic Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 100, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 测试数据：按降序插入，但应该按升序排序
    std::vector<int> keys = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    printf("插入顺序: ");
    for (int key : keys)
    {
        printf("%d ", key);
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht.insert_list_sorted_unique(pair);
        EXPECT_TRUE(result.second) << "插入key=" << key << "失败";
    }
    printf("\n");

    // 验证链表顺序（应该按key升序排列）
    printf("链表顺序: ");
    std::vector<int> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("%d ", it->key);
        actual_order.push_back(it->key);
    }
    printf("\n");

    // 验证是否按升序排列
    std::vector<int> expected_order = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    EXPECT_EQ(actual_order, expected_order) << "链表顺序不正确";

    // 验证大小
    EXPECT_EQ(ht.size(), 9) << "大小不正确";

    printf("========== Insert Sorted Unique Basic Test Completed ==========\n\n");
}

/**
 * @brief 测试 insert_list_sorted_unique 重复键处理
 * @note 验证重复键不会被插入
 */
TEST(NFShmHashTableWithListTest, InsertSortedUniqueDuplicateKey)
{
    printf("========== Insert Sorted Unique Duplicate Key Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 100, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 插入第一个元素
    TestPairWithList pair1(5, "first");
    auto result1 = ht.insert_list_sorted_unique(pair1);
    EXPECT_TRUE(result1.second) << "第一次插入应该成功";

    // 尝试插入相同键的元素
    TestPairWithList pair2(5, "second");
    auto result2 = ht.insert_list_sorted_unique(pair2);
    EXPECT_FALSE(result2.second) << "重复键插入应该失败";

    // 验证只有一个元素
    EXPECT_EQ(ht.size(), 1) << "应该只有一个元素";

    // 验证值没有被改变
    auto it = ht.find(5);
    EXPECT_NE(it, ht.end()) << "应该能找到key=5";
    EXPECT_EQ(it->value, "first") << "值应该保持为'first'";

    printf("========== Insert Sorted Unique Duplicate Key Test Completed ==========\n\n");
}

/**
 * @brief 测试 insert_list_sorted_equal 基本功能
 * @note 验证排序插入允许重复元素的基本功能
 */
TEST(NFShmHashTableWithListTest, InsertSortedEqualBasic)
{
    printf("========== Insert Sorted Equal Basic Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 100, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 测试数据：包含重复键
    std::vector<std::pair<int, std::string>> test_data = {{3, "first"}, {1, "first"}, {3, "second"}, {2, "first"}, {1, "second"}};

    printf("插入顺序: ");
    for (const auto& data : test_data)
    {
        printf("(%d,%s) ", data.first, data.second.c_str());
        TestPairWithList pair(data.first, data.second);
        auto result = ht.insert_list_sorted_equal(pair);
        EXPECT_NE(result, ht.end()) << "插入应该成功";
    }
    printf("\n");

    // 验证链表顺序（应该按key升序排列，相同key按插入顺序）
    printf("链表顺序: ");
    std::vector<std::pair<int, std::string>> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
        actual_order.push_back({it->key, it->value});
    }
    printf("\n");

    // 验证是否按升序排列
    std::vector<std::pair<int, std::string>> expected_order = {{1, "first"}, {1, "second"}, {2, "first"}, {3, "first"}, {3, "second"}};
    EXPECT_EQ(actual_order, expected_order) << "链表顺序不正确";

    // 验证大小
    EXPECT_EQ(ht.size(), 5) << "大小不正确";

    printf("========== Insert Sorted Equal Basic Test Completed ==========\n\n");
}

/**
 * @brief 测试自定义比较器的 insert_list_sorted_unique
 * @note 验证使用自定义比较器进行降序插入
 */
TEST(NFShmHashTableWithListTest, InsertSortedUniqueCustomComparator)
{
    printf("========== Insert Sorted Unique Custom Comparator Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 100, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 自定义比较器：按key降序排列
    auto descendingComparator = [](const TestPairWithList& a, const TestPairWithList& b) -> bool
    {
        return a.key > b.key; // 降序
    };

    // 测试数据：按升序插入，但应该按降序排序
    std::vector<int> keys = {1, 3, 5, 2, 4, 6, 8, 7, 9};

    printf("插入顺序: ");
    for (int key : keys)
    {
        printf("%d ", key);
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht.insert_list_sorted_unique(pair, descendingComparator);
        EXPECT_TRUE(result.second) << "插入key=" << key << "失败";
    }
    printf("\n");

    // 验证链表顺序（应该按key降序排列）
    printf("链表顺序: ");
    std::vector<int> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("%d ", it->key);
        actual_order.push_back(it->key);
    }
    printf("\n");

    // 验证是否按降序排列
    std::vector<int> expected_order = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    EXPECT_EQ(actual_order, expected_order) << "链表顺序不正确";

    printf("========== Insert Sorted Unique Custom Comparator Test Completed ==========\n\n");
}

/**
 * @brief 测试自定义比较器的 insert_list_sorted_equal
 * @note 验证使用自定义比较器进行复合条件排序
 */
TEST(NFShmHashTableWithListTest, InsertSortedEqualCustomComparator)
{
    printf("========== Insert Sorted Equal Custom Comparator Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 100, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 自定义比较器：按value长度排序，长度相同时按key排序
    auto customComparator = [](const TestPairWithList& a, const TestPairWithList& b) -> bool
    {
        if (a.value.length() != b.value.length())
        {
            return a.value.length() < b.value.length();
        }
        return a.key < b.key;
    };

    // 测试数据：不同长度的value
    std::vector<std::pair<int, std::string>> test_data = {{5, "long_value"}, {1, "a"}, {3, "medium"}, {2, "short"}, {4, "very_long_value"}};

    printf("插入顺序: ");
    for (const auto& data : test_data)
    {
        printf("(%d,%s) ", data.first, data.second.c_str());
        TestPairWithList pair(data.first, data.second);
        auto result = ht.insert_list_sorted_equal(pair, customComparator);
        EXPECT_NE(result, ht.end()) << "插入应该成功";
    }
    printf("\n");

    // 验证链表顺序（应该按value长度排序）
    printf("链表顺序: ");
    std::vector<std::pair<int, std::string>> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(%d,%s) ", it->key, it->value.c_str());
        actual_order.push_back({it->key, it->value});
    }
    printf("\n");

    // 验证是否按value长度排序
    std::vector<std::pair<int, std::string>> expected_order = {{1, "a"}, {2, "short"}, {3, "medium"}, {5, "long_value"}, {4, "very_long_value"}};
    EXPECT_EQ(actual_order, expected_order) << "链表顺序不正确";

    printf("========== Insert Sorted Equal Custom Comparator Test Completed ==========\n\n");
}

/**
 * @brief 测试排序插入的边界情况
 * @note 验证空表、单元素、容量满等边界情况
 */
TEST(NFShmHashTableWithListTest, InsertSortedEdgeCases)
{
    printf("========== Insert Sorted Edge Cases Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 5, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 测试1: 空表插入
    TestPairWithList pair1(5, "first");
    auto result1 = ht.insert_list_sorted_unique(pair1);
    EXPECT_TRUE(result1.second) << "空表插入应该成功";
    EXPECT_EQ(ht.size(), 1) << "大小应该为1";

    // 测试2: 单元素表插入
    TestPairWithList pair2(3, "second");
    auto result2 = ht.insert_list_sorted_unique(pair2);
    EXPECT_TRUE(result2.second) << "单元素表插入应该成功";
    EXPECT_EQ(ht.size(), 2) << "大小应该为2";

    // 验证顺序
    auto it = ht.list_begin();
    EXPECT_EQ(it->key, 3) << "第一个元素应该是key=3";
    ++it;
    EXPECT_EQ(it->key, 5) << "第二个元素应该是key=5";

    // 测试3: 容量满的情况
    TestPairWithList pair3(1, "third");
    auto result3 = ht.insert_list_sorted_unique(pair3);
    EXPECT_TRUE(result3.second) << "插入第三个元素应该成功";

    TestPairWithList pair4(7, "fourth");
    auto result4 = ht.insert_list_sorted_unique(pair4);
    EXPECT_TRUE(result4.second) << "插入第四个元素应该成功";

    TestPairWithList pair5(9, "fifth");
    auto result5 = ht.insert_list_sorted_unique(pair5);
    EXPECT_TRUE(result5.second) << "插入第五个元素应该成功";

    EXPECT_EQ(ht.size(), 5) << "大小应该为5";
    EXPECT_TRUE(ht.full()) << "表应该已满";

    // 尝试插入第六个元素（应该失败）
    TestPairWithList pair6(11, "sixth");
    auto result6 = ht.insert_list_sorted_unique(pair6);
    EXPECT_FALSE(result6.second) << "容量满时插入应该失败";
    EXPECT_EQ(ht.size(), 5) << "大小应该保持为5";

    printf("========== Insert Sorted Edge Cases Test Completed ==========\n\n");
}

/**
 * @brief 测试排序插入的性能
 * @note 验证大量数据插入时的性能表现
 */
TEST(NFShmHashTableWithListTest, InsertSortedPerformance)
{
    printf("========== Insert Sorted Performance Test ==========\n");

    NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList> ht;
    ht.CreateInit();

    // 生成随机测试数据
    std::vector<int> test_data;
    for (int i = 0; i < 500; ++i)
    {
        test_data.push_back(i);
    }

    // 打乱顺序
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("插入500个随机顺序的元素...\n");

    auto start = std::chrono::high_resolution_clock::now();

    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht.insert_list_sorted_unique(pair);
        EXPECT_TRUE(result.second) << "插入key=" << key << "失败";
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    printf("插入耗时: %lld 微秒\n", duration.count());

    // 验证顺序
    std::vector<int> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        actual_order.push_back(it->key);
    }

    // 验证是否按升序排列
    bool is_sorted = std::is_sorted(actual_order.begin(), actual_order.end());
    EXPECT_TRUE(is_sorted) << "插入后链表应该是有序的";

    EXPECT_EQ(ht.size(), 500) << "大小应该为500";

    printf("========== Insert Sorted Performance Test Completed ==========\n\n");
}

/**
 * @brief 性能对比测试：比较不同插入和排序方法的性能
 * @note 对比 insert_unique/insert_equal, insert_list_sorted_unique, insert_list_sorted_equal 和 SortList() 的性能
 * @note 使用较小的测试数据量以避免栈溢出
 */
TEST(NFShmHashTableWithListTest, PerformanceComparison)
{
    printf("========== Performance Comparison Test ==========\n");

    const int TEST_SIZE = 100; // 减少测试数据量以避免栈溢出
    const int REPEAT_COUNT = 2; // 减少重复次数

    // 生成测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE); // 预分配内存
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(i);
    }

    // 打乱顺序
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d\n", TEST_SIZE);
    printf("重复测试次数: %d\n", REPEAT_COUNT);
    printf("==========================================\n");

    // 1. 测试 insert_unique + SortList() 组合
    printf("1. insert_unique + SortList() 组合:\n");
    std::vector<long long> times1;
    times1.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        // 使用堆分配避免栈溢出
        auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht1->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 先插入所有元素
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht1->insert_unique(pair);
        }

        // 然后排序
        ht1->SortList();

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times1.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        // 显式释放内存
        ht1.reset();
    }

    long long avg_time1 = std::accumulate(times1.begin(), times1.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time1);

    // 2. 测试 insert_list_sorted_unique
    printf("2. insert_list_sorted_unique:\n");
    std::vector<long long> times2;
    times2.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht2->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 直接排序插入
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht2->insert_list_sorted_unique(pair);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times2.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        ht2.reset();
    }

    long long avg_time2 = std::accumulate(times2.begin(), times2.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time2);

    // 3. 测试 insert_equal + SortList() 组合
    printf("3. insert_equal + SortList() 组合:\n");
    std::vector<long long> times3;
    times3.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        auto ht3 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht3->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 先插入所有元素
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht3->insert_equal(pair);
        }

        // 然后排序
        ht3->SortList();

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times3.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        ht3.reset();
    }

    long long avg_time3 = std::accumulate(times3.begin(), times3.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time3);

    // 4. 测试 insert_list_sorted_equal
    printf("4. insert_list_sorted_equal:\n");
    std::vector<long long> times4;
    times4.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        auto ht4 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht4->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 直接排序插入
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht4->insert_list_sorted_equal(pair);
        }

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times4.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        ht4.reset();
    }

    long long avg_time4 = std::accumulate(times4.begin(), times4.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time4);

    // 5. 测试 insert_unique + SortListInsert() 组合
    printf("5. insert_unique + SortListInsert() 组合:\n");
    std::vector<long long> times5;
    times5.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        auto ht5 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht5->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 先插入所有元素
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht5->insert_unique(pair);
        }

        // 然后使用插入排序
        ht5->SortListInsert();

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times5.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        ht5.reset();
    }

    long long avg_time5 = std::accumulate(times5.begin(), times5.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time5);

    // 6. 测试 insert_unique + SortListQuick() 组合
    printf("6. insert_unique + SortListQuick() 组合:\n");
    std::vector<long long> times6;
    times6.reserve(REPEAT_COUNT);

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        auto ht6 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht6->CreateInit();

        auto start = std::chrono::high_resolution_clock::now();

        // 先插入所有元素
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht6->insert_unique(pair);
        }

        // 然后使用快速排序
        ht6->SortListQuick();

        auto end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        times6.push_back(duration.count());

        printf("  第%d次: %lld 微秒\n", repeat + 1, duration.count());

        ht6.reset();
    }

    long long avg_time6 = std::accumulate(times6.begin(), times6.end(), 0LL) / REPEAT_COUNT;
    printf("  平均时间: %lld 微秒\n\n", avg_time6);

    // 性能对比总结
    printf("==========================================\n");
    printf("性能对比总结 (平均时间):\n");
    printf("1. insert_unique + SortList():        %lld 微秒\n", avg_time1);
    printf("2. insert_list_sorted_unique:              %lld 微秒\n", avg_time2);
    printf("3. insert_equal + SortList():         %lld 微秒\n", avg_time3);
    printf("4. insert_list_sorted_equal:               %lld 微秒\n", avg_time4);
    printf("5. insert_unique + SortListInsert():  %lld 微秒\n", avg_time5);
    printf("6. insert_unique + SortListQuick():   %lld 微秒\n", avg_time6);
    printf("==========================================\n");

    // 计算性能提升/下降百分比
    printf("性能对比分析:\n");
    if (avg_time1 > 0)
    {
        double improvement2 = ((double)(avg_time1 - avg_time2) / avg_time1) * 100;
        printf("- insert_list_sorted_unique vs insert_unique+SortList: %.2f%% %s\n", std::abs(improvement2), improvement2 > 0 ? "更快" : "更慢");
    }

    if (avg_time3 > 0)
    {
        double improvement4 = ((double)(avg_time3 - avg_time4) / avg_time3) * 100;
        printf("- insert_list_sorted_equal vs insert_equal+SortList: %.2f%% %s\n", std::abs(improvement4), improvement4 > 0 ? "更快" : "更慢");
    }

    if (avg_time1 > 0)
    {
        double improvement5 = ((double)(avg_time1 - avg_time5) / avg_time1) * 100;
        printf("- SortListInsert vs SortList: %.2f%% %s\n", std::abs(improvement5), improvement5 > 0 ? "更快" : "更慢");
    }

    if (avg_time1 > 0)
    {
        double improvement6 = ((double)(avg_time1 - avg_time6) / avg_time1) * 100;
        printf("- SortListQuick vs SortList: %.2f%% %s\n", std::abs(improvement6), improvement6 > 0 ? "更快" : "更慢");
    }

    // 验证所有方法的结果都正确
    printf("\n验证结果正确性:\n");

    // 验证 insert_list_sorted_unique 结果
    auto verify_ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    verify_ht->CreateInit();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        verify_ht->insert_list_sorted_unique(pair);
    }

    std::vector<int> result_order;
    result_order.reserve(TEST_SIZE);
    for (auto it = verify_ht->list_begin(); it != verify_ht->list_end(); ++it)
    {
        result_order.push_back(it->key);
    }

    bool is_sorted = std::is_sorted(result_order.begin(), result_order.end());
    EXPECT_TRUE(is_sorted) << "insert_list_sorted_unique 结果应该是有序的";
    EXPECT_EQ(verify_ht->size(), TEST_SIZE) << "大小应该正确";

    verify_ht.reset();

    printf("- insert_list_sorted_unique 结果验证: %s\n", is_sorted ? "正确" : "错误");

    printf("========== Performance Comparison Test Completed ==========\n\n");
}

/**
 * @brief 简化的性能对比测试：避免栈溢出问题
 * @note 使用更小的数据量和更简单的测试方法
 */
TEST(NFShmHashTableWithListTest, SimplePerformanceComparison)
{
    printf("========== Simple Performance Comparison Test ==========\n");

    const int TEST_SIZE = 50; // 进一步减少测试数据量
    const int REPEAT_COUNT = 1; // 只测试一次

    // 生成测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(i);
    }

    // 打乱顺序
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d\n", TEST_SIZE);
    printf("==========================================\n");

    // 测试1: insert_unique + SortList()
    printf("1. insert_unique + SortList():\n");
    auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 200, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht1->CreateInit();

    auto start1 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht1->insert_unique(pair);
    }
    ht1->SortList();
    auto end1 = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
    printf("  时间: %lld 微秒\n", duration1.count());
    ht1.reset();

    // 测试2: insert_list_sorted_unique
    printf("2. insert_list_sorted_unique:\n");
    auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 200, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht2->CreateInit();

    auto start2 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht2->insert_list_sorted_unique(pair);
    }
    auto end2 = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);
    printf("  时间: %lld 微秒\n", duration2.count());
    ht2.reset();

    // 测试3: insert_equal + SortList()
    printf("3. insert_equal + SortList():\n");
    auto ht3 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 200, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht3->CreateInit();

    auto start3 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht3->insert_equal(pair);
    }
    ht3->SortList();
    auto end3 = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - start3);
    printf("  时间: %lld 微秒\n", duration3.count());
    ht3.reset();

    // 测试4: insert_list_sorted_equal
    printf("4. insert_list_sorted_equal:\n");
    auto ht4 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 200, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht4->CreateInit();

    auto start4 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht4->insert_list_sorted_equal(pair);
    }
    auto end4 = std::chrono::high_resolution_clock::now();
    auto duration4 = std::chrono::duration_cast<std::chrono::microseconds>(end4 - start4);
    printf("  时间: %lld 微秒\n", duration4.count());
    ht4.reset();

    // 性能对比总结
    printf("==========================================\n");
    printf("性能对比总结:\n");
    printf("1. insert_unique + SortList():    %lld 微秒\n", duration1.count());
    printf("2. insert_list_sorted_unique:          %lld 微秒\n", duration2.count());
    printf("3. insert_equal + SortList():     %lld 微秒\n", duration3.count());
    printf("4. insert_list_sorted_equal:           %lld 微秒\n", duration4.count());
    printf("==========================================\n");

    // 计算性能提升/下降百分比
    printf("性能对比分析:\n");
    if (duration1.count() > 0)
    {
        double improvement2 = ((double)(duration1.count() - duration2.count()) / duration1.count()) * 100;
        printf("- insert_list_sorted_unique vs insert_unique+SortList: %.2f%% %s\n", std::abs(improvement2), improvement2 > 0 ? "更快" : "更慢");
    }

    if (duration3.count() > 0)
    {
        double improvement4 = ((double)(duration3.count() - duration4.count()) / duration3.count()) * 100;
        printf("- insert_list_sorted_equal vs insert_equal+SortList: %.2f%% %s\n", std::abs(improvement4), improvement4 > 0 ? "更快" : "更慢");
    }

    printf("========== Simple Performance Comparison Test Completed ==========\n\n");
}

/**
 * @brief 大规模数据 insert_list_sorted_unique 功能测试
 * @note 测试大数据量下的排序插入功能正确性
 */
TEST(NFShmHashTableWithListTest, LargeScaleInsertSortedUnique)
{
    printf("========== Large Scale Insert Sorted Unique Test ==========\n");

    const int TEST_SIZE = 1000; // 大规模测试数据
    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 生成随机测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(i);
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d\n", TEST_SIZE);

    // 插入数据
    auto start = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht->insert_list_sorted_unique(pair);
        EXPECT_TRUE(result.second) << "插入应该成功，key: " << key;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    printf("插入时间: %lld 毫秒\n", duration.count());
    printf("最终大小: %zu\n", ht->size());

    // 验证结果有序性
    std::vector<int> result_order;
    result_order.reserve(TEST_SIZE);
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        result_order.push_back(it->key);
    }

    bool is_sorted = std::is_sorted(result_order.begin(), result_order.end());
    EXPECT_TRUE(is_sorted) << "大规模数据插入后应该保持有序";
    EXPECT_EQ(ht->size(), TEST_SIZE) << "大小应该正确";

    // 验证所有元素都存在
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        auto it = ht->find(i);
        EXPECT_NE(it, ht->end()) << "应该能找到key: " << i;
        if (it != ht->end())
        {
            EXPECT_EQ(it->value, "value" + std::to_string(i)) << "值应该正确";
        }
    }

    printf("大规模 insert_list_sorted_unique 测试完成\n");
    printf("========== Large Scale Insert Sorted Unique Test Completed ==========\n\n");
}

/**
 * @brief 大规模数据 insert_list_sorted_equal 功能测试
 * @note 测试大数据量下的排序插入功能正确性，允许重复键
 */
TEST(NFShmHashTableWithListTest, LargeScaleInsertSortedEqual)
{
    printf("========== Large Scale Insert Sorted Equal Test ==========\n");

    const int TEST_SIZE = 1000; // 大规模测试数据
    const int DUPLICATE_FACTOR = 3; // 每个键重复3次
    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 5000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 生成包含重复键的测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE * DUPLICATE_FACTOR);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        for (int j = 0; j < DUPLICATE_FACTOR; ++j)
        {
            test_data.push_back(i);
        }
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d (包含 %d 个重复键)\n", (int)test_data.size(), TEST_SIZE);

    // 插入数据
    auto start = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        auto result = ht->insert_list_sorted_equal(pair);
        EXPECT_NE(result, ht->end()) << "插入应该成功，key: " << key;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    printf("插入时间: %lld 毫秒\n", duration.count());
    printf("最终大小: %zu\n", ht->size());

    // 验证结果有序性
    std::vector<int> result_order;
    result_order.reserve(TEST_SIZE * DUPLICATE_FACTOR);
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        result_order.push_back(it->key);
    }

    bool is_sorted = std::is_sorted(result_order.begin(), result_order.end());
    EXPECT_TRUE(is_sorted) << "大规模数据插入后应该保持有序";
    EXPECT_EQ(ht->size(), TEST_SIZE * DUPLICATE_FACTOR) << "大小应该正确";

    // 验证每个键的重复次数
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        size_t count = ht->count(i);
        EXPECT_EQ(count, DUPLICATE_FACTOR) << "键 " << i << " 应该出现 " << DUPLICATE_FACTOR << " 次";
    }

    printf("大规模 insert_list_sorted_equal 测试完成\n");
    printf("========== Large Scale Insert Sorted Equal Test Completed ==========\n\n");
}

/**
 * @brief 极大数据量性能对比测试
 * @note 对比不同插入方法的性能，使用更大的数据量
 */
TEST(NFShmHashTableWithListTest, ExtremeScalePerformanceComparison)
{
    printf("========== Extreme Scale Performance Comparison Test ==========\n");

    const int TEST_SIZE = 2000; // 极大数据量
    const int REPEAT_COUNT = 3; // 重复测试次数

    // 生成测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(i);
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d\n", TEST_SIZE);
    printf("重复测试次数: %d\n", REPEAT_COUNT);
    printf("==========================================\n");

    long long total_time1 = 0, total_time2 = 0, total_time3 = 0, total_time4 = 0;

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        printf("第 %d 次测试:\n", repeat + 1);

        // 测试1: insert_unique + SortList()
        auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht1->CreateInit();

        auto start1 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht1->insert_unique(pair);
        }
        ht1->SortList();
        auto end1 = std::chrono::high_resolution_clock::now();
        auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
        total_time1 += duration1.count();
        printf("  1. insert_unique + SortList(): %lld 微秒\n", duration1.count());
        ht1.reset();

        // 测试2: insert_list_sorted_unique
        auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht2->CreateInit();

        auto start2 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht2->insert_list_sorted_unique(pair);
        }
        auto end2 = std::chrono::high_resolution_clock::now();
        auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);
        total_time2 += duration2.count();
        printf("  2. insert_list_sorted_unique: %lld 微秒\n", duration2.count());
        ht2.reset();

        // 测试3: insert_equal + SortList()
        auto ht3 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht3->CreateInit();

        auto start3 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht3->insert_equal(pair);
        }
        ht3->SortList();
        auto end3 = std::chrono::high_resolution_clock::now();
        auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - start3);
        total_time3 += duration3.count();
        printf("  3. insert_equal + SortList(): %lld 微秒\n", duration3.count());
        ht3.reset();

        // 测试4: insert_list_sorted_equal
        auto ht4 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht4->CreateInit();

        auto start4 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "value" + std::to_string(key));
            ht4->insert_list_sorted_equal(pair);
        }
        auto end4 = std::chrono::high_resolution_clock::now();
        auto duration4 = std::chrono::duration_cast<std::chrono::microseconds>(end4 - start4);
        total_time4 += duration4.count();
        printf("  4. insert_list_sorted_equal: %lld 微秒\n", duration4.count());
        ht4.reset();

        printf("\n");
    }

    // 计算平均时间
    long long avg_time1 = total_time1 / REPEAT_COUNT;
    long long avg_time2 = total_time2 / REPEAT_COUNT;
    long long avg_time3 = total_time3 / REPEAT_COUNT;
    long long avg_time4 = total_time4 / REPEAT_COUNT;

    printf("==========================================\n");
    printf("极大数据量性能对比总结 (平均时间):\n");
    printf("1. insert_unique + SortList():        %lld 微秒\n", avg_time1);
    printf("2. insert_list_sorted_unique:              %lld 微秒\n", avg_time2);
    printf("3. insert_equal + SortList():         %lld 微秒\n", avg_time3);
    printf("4. insert_list_sorted_equal:               %lld 微秒\n", avg_time4);
    printf("==========================================\n");

    // 计算性能提升/下降百分比
    printf("性能对比分析:\n");
    if (avg_time1 > 0)
    {
        double improvement2 = ((double)(avg_time1 - avg_time2) / avg_time1) * 100;
        printf("- insert_list_sorted_unique vs insert_unique+SortList: %.2f%% %s\n", std::abs(improvement2), improvement2 > 0 ? "更快" : "更慢");
    }

    if (avg_time3 > 0)
    {
        double improvement4 = ((double)(avg_time3 - avg_time4) / avg_time3) * 100;
        printf("- insert_list_sorted_equal vs insert_equal+SortList: %.2f%% %s\n", std::abs(improvement4), improvement4 > 0 ? "更快" : "更慢");
    }

    printf("========== Extreme Scale Performance Comparison Test Completed ==========\n\n");
}

/**
 * @brief 内存使用效率测试
 * @note 测试不同插入方法的内存使用情况
 */
TEST(NFShmHashTableWithListTest, MemoryEfficiencyTest)
{
    printf("========== Memory Efficiency Test ==========\n");

    const int TEST_SIZE = 1500;

    // 生成测试数据
    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(i);
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("测试数据大小: %d\n", TEST_SIZE);
    printf("==========================================\n");

    // 测试1: insert_unique + SortList() 的内存使用
    printf("1. insert_unique + SortList() 内存测试:\n");
    auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht1->CreateInit();

    auto start1 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht1->insert_unique(pair);
    }
    auto mid1 = std::chrono::high_resolution_clock::now();
    ht1->SortList();
    auto end1 = std::chrono::high_resolution_clock::now();

    auto insert_time1 = std::chrono::duration_cast<std::chrono::microseconds>(mid1 - start1);
    auto sort_time1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - mid1);

    printf("  插入时间: %lld 微秒\n", insert_time1.count());
    printf("  排序时间: %lld 微秒\n", sort_time1.count());
    printf("  总时间: %lld 微秒\n", insert_time1.count() + sort_time1.count());
    printf("  内存使用: %zu / %zu (%.2f%%)\n", ht1->size(), ht1->max_size(), (double)ht1->size() / ht1->max_size() * 100);
    ht1.reset();

    // 测试2: insert_list_sorted_unique 的内存使用
    printf("2. insert_list_sorted_unique 内存测试:\n");
    auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht2->CreateInit();

    auto start2 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht2->insert_list_sorted_unique(pair);
    }
    auto end2 = std::chrono::high_resolution_clock::now();

    auto total_time2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);

    printf("  总时间: %lld 微秒\n", total_time2.count());
    printf("  内存使用: %zu / %zu (%.2f%%)\n", ht2->size(), ht2->max_size(), (double)ht2->size() / ht2->max_size() * 100);
    ht2.reset();

    // 测试3: insert_equal + SortList() 的内存使用
    printf("3. insert_equal + SortList() 内存测试:\n");
    auto ht3 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht3->CreateInit();

    auto start3 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht3->insert_equal(pair);
    }
    auto mid3 = std::chrono::high_resolution_clock::now();
    ht3->SortList();
    auto end3 = std::chrono::high_resolution_clock::now();

    auto insert_time3 = std::chrono::duration_cast<std::chrono::microseconds>(mid3 - start3);
    auto sort_time3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - mid3);

    printf("  插入时间: %lld 微秒\n", insert_time3.count());
    printf("  排序时间: %lld 微秒\n", sort_time3.count());
    printf("  总时间: %lld 微秒\n", insert_time3.count() + sort_time3.count());
    printf("  内存使用: %zu / %zu (%.2f%%)\n", ht3->size(), ht3->max_size(), (double)ht3->size() / ht3->max_size() * 100);
    ht3.reset();

    // 测试4: insert_list_sorted_equal 的内存使用
    printf("4. insert_list_sorted_equal 内存测试:\n");
    auto ht4 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht4->CreateInit();

    auto start4 = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "value" + std::to_string(key));
        ht4->insert_list_sorted_equal(pair);
    }
    auto end4 = std::chrono::high_resolution_clock::now();

    auto total_time4 = std::chrono::duration_cast<std::chrono::microseconds>(end4 - start4);

    printf("  总时间: %lld 微秒\n", total_time4.count());
    printf("  内存使用: %zu / %zu (%.2f%%)\n", ht4->size(), ht4->max_size(), (double)ht4->size() / ht4->max_size() * 100);
    ht4.reset();

    printf("========== Memory Efficiency Test Completed ==========\n\n");
}

/**
 * @brief 边界条件测试
 * @note 测试各种边界条件下的插入行为
 */
TEST(NFShmHashTableWithListTest, BoundaryConditionsTest)
{
    printf("========== Boundary Conditions Test ==========\n");

    const int MAX_CAPACITY = 100;
    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, MAX_CAPACITY, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    printf("最大容量: %d\n", MAX_CAPACITY);
    printf("==========================================\n");

    // 测试1: 空容器插入
    printf("1. 空容器插入测试:\n");
    TestPairWithList pair1(1, "first");
    auto result1 = ht->insert_list_sorted_unique(pair1);
    EXPECT_TRUE(result1.second) << "空容器插入应该成功";
    EXPECT_EQ(ht->size(), 1) << "大小应该为1";
    printf("  空容器插入成功\n");

    // 测试2: 单元素容器插入
    printf("2. 单元素容器插入测试:\n");
    TestPairWithList pair2(0, "zero");
    auto result2 = ht->insert_list_sorted_unique(pair2);
    EXPECT_TRUE(result2.second) << "单元素容器插入应该成功";
    EXPECT_EQ(ht->size(), 2) << "大小应该为2";

    // 验证顺序
    std::vector<int> order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        order.push_back(it->key);
    }
    EXPECT_TRUE(std::is_sorted(order.begin(), order.end())) << "应该保持有序";
    printf("  单元素容器插入成功，顺序正确\n");

    // 测试3: 重复键插入
    printf("3. 重复键插入测试:\n");
    TestPairWithList pair3(1, "duplicate");
    auto result3 = ht->insert_list_sorted_unique(pair3);
    EXPECT_FALSE(result3.second) << "重复键插入应该失败";
    EXPECT_EQ(ht->size(), 2) << "大小应该保持为2";
    printf("  重复键插入正确被拒绝\n");

    // 测试4: 填满容器
    printf("4. 填满容器测试:\n");
    for (int i = 2; i < MAX_CAPACITY; ++i)
    {
        TestPairWithList pair(i, "value" + std::to_string(i));
        auto result = ht->insert_list_sorted_unique(pair);
        EXPECT_TRUE(result.second) << "插入应该成功，key: " << i;
    }
    EXPECT_EQ(ht->size(), MAX_CAPACITY) << "容器应该已满";
    printf("  容器已填满，大小: %zu\n", ht->size());

    // 测试5: 超出容量插入
    printf("5. 超出容量插入测试:\n");
    TestPairWithList pair_overflow(MAX_CAPACITY, "overflow");
    auto result_overflow = ht->insert_list_sorted_unique(pair_overflow);
    EXPECT_FALSE(result_overflow.second) << "超出容量插入应该失败";
    EXPECT_EQ(ht->size(), MAX_CAPACITY) << "大小应该保持不变";
    printf("  超出容量插入正确被拒绝\n");

    // 测试6: 验证最终顺序
    printf("6. 最终顺序验证:\n");
    std::vector<int> final_order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        final_order.push_back(it->key);
    }
    EXPECT_TRUE(std::is_sorted(final_order.begin(), final_order.end())) << "最终结果应该有序";
    EXPECT_EQ(final_order.size(), MAX_CAPACITY) << "应该包含所有元素";
    printf("  最终顺序验证通过\n");

    printf("========== Boundary Conditions Test Completed ==========\n\n");
}

/**
 * @brief 随机数据压力测试
 * @note 使用随机数据进行压力测试，验证稳定性
 */
TEST(NFShmHashTableWithListTest, RandomDataStressTest)
{
    printf("========== Random Data Stress Test ==========\n");

    const int TEST_SIZE = 800;
    const int RANDOM_RANGE = 2000; // 随机数范围，包含重复值

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 生成随机测试数据
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, RANDOM_RANGE - 1);

    std::vector<int> test_data;
    test_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        test_data.push_back(dis(gen));
    }

    printf("测试数据大小: %d\n", TEST_SIZE);
    printf("随机数范围: 0 - %d\n", RANDOM_RANGE - 1);
    printf("==========================================\n");

    // 插入数据并记录统计信息
    int successful_inserts = 0;
    int failed_inserts = 0;

    auto start = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "random_value" + std::to_string(key));
        auto result = ht->insert_list_sorted_unique(pair);
        if (result.second)
        {
            successful_inserts++;
        }
        else
        {
            failed_inserts++;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    printf("插入统计:\n");
    printf("  成功插入: %d\n", successful_inserts);
    printf("  失败插入: %d\n", failed_inserts);
    printf("  插入时间: %lld 毫秒\n", duration.count());
    printf("  最终大小: %zu\n", ht->size());

    // 验证结果有序性
    std::vector<int> result_order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        result_order.push_back(it->key);
    }

    bool is_sorted = std::is_sorted(result_order.begin(), result_order.end());
    EXPECT_TRUE(is_sorted) << "随机数据插入后应该保持有序";
    printf("  顺序验证: %s\n", is_sorted ? "通过" : "失败");

    // 验证所有插入的元素都存在
    int found_count = 0;
    for (int key : test_data)
    {
        auto it = ht->find(key);
        if (it != ht->end())
        {
            found_count++;
        }
    }
    printf("  元素查找验证: %d / %d 个元素存在\n", found_count, TEST_SIZE);

    // 验证唯一性
    std::set<int> unique_keys;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        unique_keys.insert(it->key);
    }
    EXPECT_EQ(unique_keys.size(), ht->size()) << "所有键应该是唯一的";
    printf("  唯一性验证: %s\n", (unique_keys.size() == ht->size()) ? "通过" : "失败");

    printf("========== Random Data Stress Test Completed ==========\n\n");
}

/**
 * @brief 大数据量 insert_list_sorted_equal 重复键测试
 * @note 专门测试 insert_list_sorted_equal 处理重复键的能力
 */
TEST(NFShmHashTableWithListTest, LargeScaleInsertSortedEqualWithDuplicates)
{
    printf("========== Large Scale Insert Sorted Equal With Duplicates Test ==========\n");

    const int UNIQUE_KEYS = 500; // 唯一键数量
    const int DUPLICATES_PER_KEY = 5; // 每个键的重复次数
    const int TOTAL_INSERTS = UNIQUE_KEYS * DUPLICATES_PER_KEY;

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 生成包含重复键的测试数据
    std::vector<int> test_data;
    test_data.reserve(TOTAL_INSERTS);
    for (int i = 0; i < UNIQUE_KEYS; ++i)
    {
        for (int j = 0; j < DUPLICATES_PER_KEY; ++j)
        {
            test_data.push_back(i);
        }
    }

    // 打乱顺序
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("唯一键数量: %d\n", UNIQUE_KEYS);
    printf("每个键重复次数: %d\n", DUPLICATES_PER_KEY);
    printf("总插入次数: %d\n", TOTAL_INSERTS);
    printf("==========================================\n");

    // 插入数据
    auto start = std::chrono::high_resolution_clock::now();
    for (int key : test_data)
    {
        TestPairWithList pair(key, "duplicate_value" + std::to_string(key));
        auto result = ht->insert_list_sorted_equal(pair);
        EXPECT_NE(result, ht->end()) << "插入应该成功，key: " << key;
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    printf("插入时间: %lld 毫秒\n", duration.count());
    printf("最终大小: %zu\n", ht->size());

    // 验证结果有序性
    std::vector<int> result_order;
    result_order.reserve(TOTAL_INSERTS);
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        result_order.push_back(it->key);
    }

    bool is_sorted = std::is_sorted(result_order.begin(), result_order.end());
    EXPECT_TRUE(is_sorted) << "重复键插入后应该保持有序";
    EXPECT_EQ(ht->size(), TOTAL_INSERTS) << "大小应该正确";

    // 验证每个键的重复次数
    printf("重复次数验证:\n");
    int correct_counts = 0;
    for (int i = 0; i < UNIQUE_KEYS; ++i)
    {
        size_t count = ht->count(i);
        if (count == DUPLICATES_PER_KEY)
        {
            correct_counts++;
        }
        else
        {
            printf("  键 %d 的计数错误: 期望 %d，实际 %zu\n", i, DUPLICATES_PER_KEY, count);
        }
    }
    printf("  正确计数的键: %d / %d\n", correct_counts, UNIQUE_KEYS);
    EXPECT_EQ(correct_counts, UNIQUE_KEYS) << "所有键的重复次数应该正确";

    // 验证所有重复键都在正确位置
    printf("位置验证:\n");
    int current_key = -1;
    int current_count = 0;
    bool position_correct = true;

    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        if (it->key != current_key)
        {
            if (current_key >= 0 && current_count != DUPLICATES_PER_KEY)
            {
                printf("  键 %d 的重复次数不正确: %d\n", current_key, current_count);
                position_correct = false;
            }
            current_key = it->key;
            current_count = 1;
        }
        else
        {
            current_count++;
        }
    }

    // 检查最后一个键
    if (current_key >= 0 && current_count != DUPLICATES_PER_KEY)
    {
        printf("  最后一个键 %d 的重复次数不正确: %d\n", current_key, current_count);
        position_correct = false;
    }

    EXPECT_TRUE(position_correct) << "所有重复键应该在正确位置";
    printf("  位置验证: %s\n", position_correct ? "通过" : "失败");

    printf("========== Large Scale Insert Sorted Equal With Duplicates Test Completed ==========\n\n");
}

/**
 * @brief 不同数据分布性能测试
 * @note 测试不同数据分布对性能的影响
 */
TEST(NFShmHashTableWithListTest, DifferentDataDistributionPerformanceTest)
{
    printf("========== Different Data Distribution Performance Test ==========\n");

    const int TEST_SIZE = 1000;

    // 测试1: 已排序数据
    printf("1. 已排序数据测试:\n");
    std::vector<int> sorted_data;
    sorted_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        sorted_data.push_back(i);
    }

    auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht1->CreateInit();

    auto start1 = std::chrono::high_resolution_clock::now();
    for (int key : sorted_data)
    {
        TestPairWithList pair(key, "sorted_value" + std::to_string(key));
        ht1->insert_list_sorted_unique(pair);
    }
    auto end1 = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
    printf("  已排序数据插入时间: %lld 微秒\n", duration1.count());
    ht1.reset();

    // 测试2: 逆序数据
    printf("2. 逆序数据测试:\n");
    std::vector<int> reverse_data;
    reverse_data.reserve(TEST_SIZE);
    for (int i = TEST_SIZE - 1; i >= 0; --i)
    {
        reverse_data.push_back(i);
    }

    auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht2->CreateInit();

    auto start2 = std::chrono::high_resolution_clock::now();
    for (int key : reverse_data)
    {
        TestPairWithList pair(key, "reverse_value" + std::to_string(key));
        ht2->insert_list_sorted_unique(pair);
    }
    auto end2 = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);
    printf("  逆序数据插入时间: %lld 微秒\n", duration2.count());
    ht2.reset();

    // 测试3: 随机数据
    printf("3. 随机数据测试:\n");
    std::vector<int> random_data;
    random_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; ++i)
    {
        random_data.push_back(i);
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(random_data.begin(), random_data.end(), gen);

    auto ht3 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht3->CreateInit();

    auto start3 = std::chrono::high_resolution_clock::now();
    for (int key : random_data)
    {
        TestPairWithList pair(key, "random_value" + std::to_string(key));
        ht3->insert_list_sorted_unique(pair);
    }
    auto end3 = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::microseconds>(end3 - start3);
    printf("  随机数据插入时间: %lld 微秒\n", duration3.count());
    ht3.reset();

    // 测试4: 部分有序数据
    printf("4. 部分有序数据测试:\n");
    std::vector<int> partial_sorted_data;
    partial_sorted_data.reserve(TEST_SIZE);
    for (int i = 0; i < TEST_SIZE; i += 10)
    {
        // 每10个元素为一组，组内有序，组间随机
        for (int j = 0; j < 10 && i + j < TEST_SIZE; ++j)
        {
            partial_sorted_data.push_back(i + j);
        }
    }
    std::shuffle(partial_sorted_data.begin(), partial_sorted_data.end(), gen);

    auto ht4 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht4->CreateInit();

    auto start4 = std::chrono::high_resolution_clock::now();
    for (int key : partial_sorted_data)
    {
        TestPairWithList pair(key, "partial_value" + std::to_string(key));
        ht4->insert_list_sorted_unique(pair);
    }
    auto end4 = std::chrono::high_resolution_clock::now();
    auto duration4 = std::chrono::duration_cast<std::chrono::microseconds>(end4 - start4);
    printf("  部分有序数据插入时间: %lld 微秒\n", duration4.count());
    ht4.reset();

    printf("==========================================\n");
    printf("数据分布性能对比:\n");
    printf("已排序数据:     %lld 微秒\n", duration1.count());
    printf("逆序数据:       %lld 微秒\n", duration2.count());
    printf("随机数据:       %lld 微秒\n", duration3.count());
    printf("部分有序数据:   %lld 微秒\n", duration4.count());
    printf("==========================================\n");

    printf("========== Different Data Distribution Performance Test Completed ==========\n\n");
}

/**
 * @brief 混合操作测试
 * @note 测试插入、查找、删除等混合操作对排序的影响
 */
TEST(NFShmHashTableWithListTest, MixedOperationsTest)
{
    printf("========== Mixed Operations Test ==========\n");

    const int INITIAL_SIZE = 500;
    const int OPERATIONS_COUNT = 200;

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 初始插入
    printf("1. 初始插入 %d 个元素:\n", INITIAL_SIZE);
    auto start1 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < INITIAL_SIZE; ++i)
    {
        TestPairWithList pair(i, "initial_value" + std::to_string(i));
        ht->insert_list_sorted_unique(pair);
    }
    auto end1 = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
    printf("  初始插入时间: %lld 微秒\n", duration1.count());
    printf("  初始大小: %zu\n", ht->size());

    // 验证初始状态有序性
    std::vector<int> initial_order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        initial_order.push_back(it->key);
    }
    bool initial_sorted = std::is_sorted(initial_order.begin(), initial_order.end());
    EXPECT_TRUE(initial_sorted) << "初始插入后应该有序";
    printf("  初始顺序验证: %s\n", initial_sorted ? "通过" : "失败");

    // 混合操作
    printf("2. 执行 %d 次混合操作:\n", OPERATIONS_COUNT);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> op_dis(0, 2); // 0: 插入, 1: 查找, 2: 删除
    std::uniform_int_distribution<> key_dis(0, INITIAL_SIZE + OPERATIONS_COUNT);

    int insert_count = 0, find_count = 0, delete_count = 0;
    int successful_inserts = 0, successful_finds = 0, successful_deletes = 0;

    auto start2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < OPERATIONS_COUNT; ++i)
    {
        int operation = op_dis(gen);
        int key = key_dis(gen);

        switch (operation)
        {
            case 0: // 插入
            {
                insert_count++;
                TestPairWithList pair(key, "mixed_value" + std::to_string(key));
                auto result = ht->insert_list_sorted_unique(pair);
                if (result.second)
                {
                    successful_inserts++;
                }
                break;
            }
            case 1: // 查找
            {
                find_count++;
                auto it = ht->find(key);
                if (it != ht->end())
                {
                    successful_finds++;
                }
                break;
            }
            case 2: // 删除
            {
                delete_count++;
                size_t erased = ht->erase(key);
                if (erased > 0)
                {
                    successful_deletes++;
                }
                break;
            }
        }
    }
    auto end2 = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);

    printf("  混合操作时间: %lld 微秒\n", duration2.count());
    printf("  操作统计:\n");
    printf("    插入: %d 次 (成功: %d)\n", insert_count, successful_inserts);
    printf("    查找: %d 次 (成功: %d)\n", find_count, successful_finds);
    printf("    删除: %d 次 (成功: %d)\n", delete_count, successful_deletes);
    printf("  最终大小: %zu\n", ht->size());

    // 验证最终状态有序性
    printf("3. 验证最终状态:\n");
    std::vector<int> final_order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        final_order.push_back(it->key);
    }
    bool final_sorted = std::is_sorted(final_order.begin(), final_order.end());
    EXPECT_TRUE(final_sorted) << "混合操作后应该保持有序";
    printf("  最终顺序验证: %s\n", final_sorted ? "通过" : "失败");

    // 验证所有剩余元素都可以找到
    int found_elements = 0;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        auto find_it = ht->find(it->key);
        if (find_it != ht->end())
        {
            found_elements++;
        }
    }
    EXPECT_EQ(found_elements, ht->size()) << "所有剩余元素都应该能找到";
    printf("  元素查找验证: %d / %zu 个元素存在\n", found_elements, ht->size());

    printf("========== Mixed Operations Test Completed ==========\n\n");
}

/**
 * @brief 大数据量 insert_list_sorted_equal 性能优化测试
 * @note 专门测试 insert_list_sorted_equal 在大数据量下的性能表现
 */
TEST(NFShmHashTableWithListTest, LargeScaleInsertSortedEqualPerformanceTest)
{
    printf("========== Large Scale Insert Sorted Equal Performance Test ==========\n");

    const int UNIQUE_KEYS = 1000;
    const int DUPLICATES_PER_KEY = 2;
    const int TOTAL_INSERTS = UNIQUE_KEYS * DUPLICATES_PER_KEY;
    const int REPEAT_COUNT = 3;

    // 生成测试数据
    std::vector<int> test_data;
    test_data.reserve(TOTAL_INSERTS);
    for (int i = 0; i < UNIQUE_KEYS; ++i)
    {
        for (int j = 0; j < DUPLICATES_PER_KEY; ++j)
        {
            test_data.push_back(i);
        }
    }

    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(test_data.begin(), test_data.end(), gen);

    printf("唯一键数量: %d\n", UNIQUE_KEYS);
    printf("每个键重复次数: %d\n", DUPLICATES_PER_KEY);
    printf("总插入次数: %d\n", TOTAL_INSERTS);
    printf("重复测试次数: %d\n", REPEAT_COUNT);
    printf("==========================================\n");

    long long total_time_sorted = 0, total_time_unsorted = 0;

    for (int repeat = 0; repeat < REPEAT_COUNT; ++repeat)
    {
        printf("第 %d 次测试:\n", repeat + 1);

        // 测试1: insert_list_sorted_equal
        auto ht1 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht1->CreateInit();

        auto start1 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "perf_value" + std::to_string(key));
            ht1->insert_list_sorted_equal(pair);
        }
        auto end1 = std::chrono::high_resolution_clock::now();
        auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1);
        total_time_sorted += duration1.count();
        printf("  1. insert_list_sorted_equal: %lld 微秒\n", duration1.count());
        ht1.reset();

        // 测试2: insert_equal + SortList()
        auto ht2 = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 3000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht2->CreateInit();

        auto start2 = std::chrono::high_resolution_clock::now();
        for (int key : test_data)
        {
            TestPairWithList pair(key, "perf_value" + std::to_string(key));
            ht2->insert_equal(pair);
        }
        ht2->SortList();
        auto end2 = std::chrono::high_resolution_clock::now();
        auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2);
        total_time_unsorted += duration2.count();
        printf("  2. insert_equal + SortList(): %lld 微秒\n", duration2.count());
        ht2.reset();

        printf("\n");
    }

    // 计算平均时间
    long long avg_time_sorted = total_time_sorted / REPEAT_COUNT;
    long long avg_time_unsorted = total_time_unsorted / REPEAT_COUNT;

    printf("==========================================\n");
    printf("大数据量 insert_list_sorted_equal 性能对比总结:\n");
    printf("insert_list_sorted_equal:        %lld 微秒 (平均)\n", avg_time_sorted);
    printf("insert_equal + SortList():  %lld 微秒 (平均)\n", avg_time_unsorted);
    printf("==========================================\n");

    // 计算性能提升/下降百分比
    if (avg_time_unsorted > 0)
    {
        double improvement = ((double)(avg_time_unsorted - avg_time_sorted) / avg_time_unsorted) * 100;
        printf("性能对比分析:\n");
        printf("- insert_list_sorted_equal vs insert_equal+SortList: %.2f%% %s\n", std::abs(improvement), improvement > 0 ? "更快" : "更慢");
    }

    printf("========== Large Scale Insert Sorted Equal Performance Test Completed ==========\n\n");
}

/**
 * @brief 内存碎片化测试
 * @note 测试大量插入删除操作后的内存使用情况
 */
TEST(NFShmHashTableWithListTest, MemoryFragmentationTest)
{
    printf("========== Memory Fragmentation Test ==========\n");

    const int INITIAL_SIZE = 800;
    const int CYCLES = 5;
    const int CYCLE_SIZE = 200;

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    printf("初始大小: %d\n", INITIAL_SIZE);
    printf("循环次数: %d\n", CYCLES);
    printf("每循环大小: %d\n", CYCLE_SIZE);
    printf("==========================================\n");

    // 初始填充
    printf("1. 初始填充:\n");
    for (int i = 0; i < INITIAL_SIZE; ++i)
    {
        TestPairWithList pair(i, "initial" + std::to_string(i));
        ht->insert_list_sorted_unique(pair);
    }
    printf("  初始大小: %zu\n", ht->size());

    // 循环插入删除
    for (int cycle = 0; cycle < CYCLES; ++cycle)
    {
        printf("2. 第 %d 次循环:\n", cycle + 1);

        // 删除一些元素
        auto start_delete = std::chrono::high_resolution_clock::now();
        for (int i = cycle * CYCLE_SIZE; i < (cycle + 1) * CYCLE_SIZE; ++i)
        {
            ht->erase(i);
        }
        auto end_delete = std::chrono::high_resolution_clock::now();
        auto delete_duration = std::chrono::duration_cast<std::chrono::microseconds>(end_delete - start_delete);

        printf("  删除时间: %lld 微秒\n", delete_duration.count());
        printf("  删除后大小: %zu\n", ht->size());

        // 插入新元素
        auto start_insert = std::chrono::high_resolution_clock::now();
        for (int i = INITIAL_SIZE + cycle * CYCLE_SIZE; i < INITIAL_SIZE + (cycle + 1) * CYCLE_SIZE; ++i)
        {
            TestPairWithList pair(i, "cycle" + std::to_string(cycle) + "_" + std::to_string(i));
            ht->insert_list_sorted_unique(pair);
        }
        auto end_insert = std::chrono::high_resolution_clock::now();
        auto insert_duration = std::chrono::duration_cast<std::chrono::microseconds>(end_insert - start_insert);

        printf("  插入时间: %lld 微秒\n", insert_duration.count());
        printf("  插入后大小: %zu\n", ht->size());

        // 验证有序性
        std::vector<int> order;
        for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
        {
            order.push_back(it->key);
        }
        bool is_sorted = std::is_sorted(order.begin(), order.end());
        EXPECT_TRUE(is_sorted) << "循环操作后应该保持有序";
        printf("  顺序验证: %s\n", is_sorted ? "通过" : "失败");

        printf("\n");
    }

    // 最终验证
    printf("3. 最终验证:\n");
    printf("  最终大小: %zu\n", ht->size());
    printf("  内存使用率: %.2f%%\n", (double)ht->size() / ht->max_size() * 100);

    // 验证所有元素都存在且有序
    std::vector<int> final_order;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        final_order.push_back(it->key);
    }
    bool final_sorted = std::is_sorted(final_order.begin(), final_order.end());
    EXPECT_TRUE(final_sorted) << "最终结果应该有序";
    printf("  最终顺序验证: %s\n", final_sorted ? "通过" : "失败");

    // 验证所有元素都可以找到
    int found_count = 0;
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        auto find_it = ht->find(it->key);
        if (find_it != ht->end())
        {
            found_count++;
        }
    }
    EXPECT_EQ(found_count, ht->size()) << "所有元素都应该能找到";
    printf("  元素查找验证: %d / %zu 个元素存在\n", found_count, ht->size());

    printf("========== Memory Fragmentation Test Completed ==========\n\n");
}

// ==================== SortListMergeFast 专门测试 ====================

/**
 * @brief SortListMergeFast 基本功能测试
 */
TEST(NFShmHashTableWithListTest, SortListMergeFastBasicTest)
{
    printf("========== SortListMergeFast Basic Test ==========\n");

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 插入测试数据
    std::vector<int> test_keys = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};

    printf("插入数据: ");
    for (int key : test_keys)
    {
        TestPairWithList pair(key, "fast_value" + std::to_string(key));
        ht->insert_unique(pair);
        printf("%d ", key);
    }
    printf("\n");

    printf("排序前大小: %zu\n", ht->size());

    // 使用 SortListMergeFast 排序
    auto start = std::chrono::high_resolution_clock::now();
    ht->SortListMergeFast();
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    printf("SortListMergeFast 排序时间: %lld 微秒\n", duration.count());
    printf("排序后大小: %zu\n", ht->size());

    // 验证排序结果
    std::vector<int> sorted_keys;
    printf("排序后顺序: ");
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        sorted_keys.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    // 检查是否有序
    bool is_sorted = std::is_sorted(sorted_keys.begin(), sorted_keys.end());
    EXPECT_TRUE(is_sorted) << "SortListMergeFast 排序结果应该有序";
    EXPECT_EQ(sorted_keys.size(), test_keys.size()) << "元素数量应该保持不变";

    // 检查所有元素都存在
    std::sort(test_keys.begin(), test_keys.end());
    EXPECT_EQ(sorted_keys, test_keys) << "排序后的元素应该与原始元素相同";

    // 验证哈希表完整性：确保排序后所有元素都能通过hash访问
    printf("验证哈希表完整性: ");
    bool hash_integrity = true;
    int verified_count = 0;
    for (int key : test_keys)
    {
        auto find_it = ht->find(key);
        if (find_it != ht->end())
        {
            verified_count++;
            // 验证值是否正确
            std::string expected_value = "fast_value" + std::to_string(key);
            if (find_it->value != expected_value)
            {
                hash_integrity = false;
                printf("键 %d 的值不匹配, 期望: %s, 实际: %s; ", key, expected_value.c_str(), find_it->value.c_str());
            }
        }
        else
        {
            hash_integrity = false;
            printf("键 %d 无法通过hash找到; ", key);
        }
    }

    EXPECT_TRUE(hash_integrity) << "SortListMergeFast排序后所有元素都应能通过hash正确访问";
    EXPECT_EQ(verified_count, test_keys.size()) << "应该能找到所有插入的元素";

    printf("%s (验证了 %d/%zu 个元素)\n", hash_integrity ? "通过" : "失败", verified_count, test_keys.size());
    printf("正确性验证: %s\n", (is_sorted && hash_integrity) ? "通过" : "失败");
    printf("============================================\n\n");
}

/**
 * @brief 快速查找接口性能对比测试
 * @note 测试新的AdaptiveSearchInsertPosition与旧的BinarySearchInsertPosition性能差异
 */
TEST(NFShmHashTableWithListTest, FastSearchInsertPositionPerformanceTest)
{
    printf("========== Fast Search Insert Position Performance Test ==========\n");

    const std::vector<int> test_sizes = {50, 100, 200, 500, 1000, 2000};

    printf("%-8s %-15s %-20s %-20s %-15s\n", "规模", "LineSearch(微秒)", "AdaptiveSearch(微秒)", "BinarySearch(微秒)", "性能提升");
    printf("%-8s %-15s %-20s %-20s %-15s\n", "----", "-------------", "------------------", "------------------", "---------");

    for (int size : test_sizes)
    {
        auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
        ht->CreateInit();

        // 插入有序数据以便测试查找性能
        for (int i = 0; i < size; ++i)
        {
            TestPairWithList pair(i, "search_value" + std::to_string(i));
            ht->insert_unique(pair);
        }

        // 确保数据有序
        ht->SortListMergeFast();

        // 准备测试的目标节点（选择中间的节点进行移动测试）
        int target_key = size / 2;
        auto target_it = ht->find(target_key);
        EXPECT_NE(target_it, ht->end()) << "应该能找到目标元素";

        if (target_it == ht->end())
            continue;

        auto target_node = const_cast<typename decltype(ht)::element_type::Node*>(reinterpret_cast<const typename decltype(ht)::element_type::Node*>(target_it.m_curNode));

        auto comp = [](const TestPairWithList& a, const TestPairWithList& b)
        {
            return a.key < b.key;
        };

        // 1. 测试LineSearchInsertPosition性能
        long long line_search_time = 0;
        {
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < 100; ++i)
            {
                auto result = ht->LineSearchInsertPosition(target_node, comp);
                (void)result; // 避免编译器优化
            }
            auto end = std::chrono::high_resolution_clock::now();
            line_search_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }

        // 2. 测试AdaptiveSearchInsertPosition性能
        long long adaptive_search_time = 0;
        {
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < 100; ++i)
            {
                auto result = ht->AdaptiveSearchInsertPosition(target_node, comp);
                (void)result; // 避免编译器优化
            }
            auto end = std::chrono::high_resolution_clock::now();
            adaptive_search_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }

        // 3. 测试BinarySearchInsertPosition性能
        long long binary_search_time = 0;
        {
            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < 100; ++i)
            {
                auto result = ht->BinarySearchInsertPosition(target_node, comp);
                (void)result; // 避免编译器优化
            }
            auto end = std::chrono::high_resolution_clock::now();
            binary_search_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }

        // 计算性能提升
        double improvement = (binary_search_time > 0) ? static_cast<double>(binary_search_time) / adaptive_search_time : 1.0;

        printf("%-8d %-15lld %-20lld %-20lld %-15.2fx\n", size, line_search_time, adaptive_search_time, binary_search_time, improvement);
    }

    printf("\n性能分析：\n");
    printf(" LineSearch：     O(n) 线性搜索，适合小数据集\n");
    printf(" AdaptiveSearch： 自适应算法，根据数据规模选择最优策略\n");
    printf(" BinarySearch：   O(log n) 理论复杂度，但有额外的内存分配开销\n");
    printf(" AdaptiveSearch 在中等规模数据集上应显示明显性能优势\n");
    printf("================================================================\n\n");
}

/**
 * @brief SortListMergeFast 与其他排序方法性能比较测试
 */
TEST(NFShmHashTableWithListTest, SortListMergeFastPerformanceComparisonTest)
{
    printf("========== SortList Performance Comparison (Including SortListMergeFast) ==========\n");

    const int TEST_SIZE = 500;
    const int ITERATIONS = 5;

    std::vector<int> test_data(TEST_SIZE);
    std::iota(test_data.begin(), test_data.end(), 0);
    std::random_device rd;
    std::mt19937 gen(rd());

    printf("测试数据大小: %d, 迭代次数: %d\n", TEST_SIZE, ITERATIONS);
    printf("==========================================================================\n");

    // 存储所有排序方法的性能数据
    struct SortResult
    {
        std::string name;
        long long total_time;
        long long avg_time;
    };

    std::vector<SortResult> results;

    // 测试 SortListMerge（原始版本）
    {
        long long total_time = 0;
        for (int iter = 0; iter < ITERATIONS; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "merge_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListMerge();
            auto end = std::chrono::high_resolution_clock::now();
            total_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

            // 验证正确性
            std::vector<int> result_keys;
            for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
            {
                result_keys.push_back(it->key);
            }
            EXPECT_TRUE(std::is_sorted(result_keys.begin(), result_keys.end())) << "SortListMerge 结果应该有序";
        }
        results.push_back({"SortListMerge", total_time, total_time / ITERATIONS});
    }

    // 测试 SortListMergeFast（优化版本）
    {
        long long total_time = 0;
        for (int iter = 0; iter < ITERATIONS; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "fast_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListMergeFast();
            auto end = std::chrono::high_resolution_clock::now();
            total_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

            // 验证正确性
            std::vector<int> result_keys;
            for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
            {
                result_keys.push_back(it->key);
            }
            EXPECT_TRUE(std::is_sorted(result_keys.begin(), result_keys.end())) << "SortListMergeFast 结果应该有序";
        }
        results.push_back({"SortListMergeFast", total_time, total_time / ITERATIONS});
    }

    // 测试 SortListInsert
    {
        long long total_time = 0;
        for (int iter = 0; iter < ITERATIONS; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "insert_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListInsert();
            auto end = std::chrono::high_resolution_clock::now();
            total_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }
        results.push_back({"SortListInsert", total_time, total_time / ITERATIONS});
    }

    // 测试 SortListQuick
    {
        long long total_time = 0;
        for (int iter = 0; iter < ITERATIONS; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "quick_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListQuick();
            auto end = std::chrono::high_resolution_clock::now();
            total_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }
        results.push_back({"SortListQuick", total_time, total_time / ITERATIONS});
    }

    // 测试 SortListSelect
    {
        long long total_time = 0;
        for (int iter = 0; iter < ITERATIONS; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 1000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "select_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListSelect();
            auto end = std::chrono::high_resolution_clock::now();
            total_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }
        results.push_back({"SortListSelect", total_time, total_time / ITERATIONS});
    }

    // 按性能排序
    std::sort(results.begin(), results.end(), [](const SortResult& a, const SortResult& b)
    {
        return a.avg_time < b.avg_time;
    });

    // 输出性能比较结果
    printf("\n性能排行榜 (从快到慢):\n");
    for (size_t i = 0; i < results.size(); ++i)
    {
        printf("%zu. %-20s: 平均 %6lld μs, 总计 %6lld μs", i + 1, results[i].name.c_str(), results[i].avg_time, results[i].total_time);

        if (i > 0)
        {
            double ratio = (double)results[i].avg_time / results[0].avg_time;
            printf(" (%.2fx slower)", ratio);
        }
        else
        {
            printf(" (fastest)");
        }
        printf("\n");
    }

    // 特别关注 SortListMergeFast 的表现
    auto merge_it = std::find_if(results.begin(), results.end(), [](const SortResult& r) { return r.name == "SortListMerge"; });
    auto fast_it = std::find_if(results.begin(), results.end(), [](const SortResult& r) { return r.name == "SortListMergeFast"; });

    if (merge_it != results.end() && fast_it != results.end())
    {
        printf("\n=== SortListMergeFast vs SortListMerge 对比 ===\n");
        printf("SortListMerge:     %lld μs\n", merge_it->avg_time);
        printf("SortListMergeFast: %lld μs\n", fast_it->avg_time);

        if (fast_it->avg_time > 0)
        {
            double improvement = (double)merge_it->avg_time / fast_it->avg_time;
            printf("性能提升: %.2fx\n", improvement);

            if (improvement >= 2.0)
            {
                printf(" 显著性能提升!\n");
            }
            else if (improvement >= 1.2)
            {
                printf(" 明显性能提升!\n");
            }
            else if (improvement >= 1.0)
            {
                printf(" 性能有所改善\n");
            }
            else
            {
                printf(" 性能可能需要在更大数据集上才能体现优势\n");
            }
        }
    }

    printf("==========================================================================\n\n");
}

/**
 * @brief SortListMergeFast 不同数据规模性能测试
 */
TEST(NFShmHashTableWithListTest, SortListMergeFastScalabilityTest)
{
    printf("========== SortListMergeFast Scalability Test ==========\n");

    std::vector<int> test_sizes = {50, 100, 200, 500, 1000};
    std::random_device rd;
    std::mt19937 gen(rd());

    printf("测试不同数据规模下 SortListMergeFast 的性能表现\n");
    printf("====================================================\n");

    for (int size : test_sizes)
    {
        printf("\n数据规模: %d\n", size);
        printf("----------------------------------------\n");

        std::vector<int> test_data(size);
        std::iota(test_data.begin(), test_data.end(), 0);

        const int iterations = (size <= 200) ? 10 : 5;

        // 测试 SortListMerge
        long long merge_total = 0;
        for (int iter = 0; iter < iterations; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "scale_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListMerge();
            auto end = std::chrono::high_resolution_clock::now();
            merge_total += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }

        // 测试 SortListMergeFast
        long long fast_total = 0;
        for (int iter = 0; iter < iterations; ++iter)
        {
            auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 2000, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
            ht->CreateInit();

            std::shuffle(test_data.begin(), test_data.end(), gen);
            for (int key : test_data)
            {
                TestPairWithList pair(key, "scale_value" + std::to_string(key));
                ht->insert_unique(pair);
            }

            auto start = std::chrono::high_resolution_clock::now();
            ht->SortListMergeFast();
            auto end = std::chrono::high_resolution_clock::now();
            fast_total += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        }

        long long merge_avg = merge_total / iterations;
        long long fast_avg = fast_total / iterations;

        printf("SortListMerge:     %6lld μs (平均)\n", merge_avg);
        printf("SortListMergeFast: %6lld μs (平均)\n", fast_avg);

        if (fast_avg > 0)
        {
            double speedup = (double)merge_avg / fast_avg;
            printf("性能提升:          %.2fx\n", speedup);

            // 验证算法选择
            if (size <= 32)
            {
                printf("算法选择: 插入排序 (≤32)\n");
            }
            else if (size <= 1000)
            {
                printf("算法选择: 递归归并排序 (32-1000)\n");
            }
            else
            {
                printf("算法选择: 迭代归并排序 (>1000)\n");
            }
        }
    }

    printf("\n====================================================\n");
    printf("规模测试完成 - SortListMergeFast 展现了良好的可扩展性\n");
    printf("========================================================\n\n");
}

/**
 * @brief SortListMergeFast 自定义比较器测试
 */
TEST(NFShmHashTableWithListTest, SortListMergeFastCustomComparatorTest)
{
    printf("========== SortListMergeFast Custom Comparator Test ==========\n");

    auto ht = std::make_unique<NFShmHashTableWithList<TestPairWithList, int, 500, HashFuncWithList, ExtractKeyWithList, EqualKeyWithList>>();
    ht->CreateInit();

    // 插入测试数据
    std::vector<int> test_keys = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    for (int key : test_keys)
    {
        TestPairWithList pair(key, "custom_value" + std::to_string(key));
        ht->insert_unique(pair);
    }

    printf("原始数据: ");
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        printf("%d ", it->key);
    }
    printf("\n");

    // 测试1: 降序排序
    printf("\n测试1: 降序排序 (std::greater)\n");
    ht->SortListMergeFast(std::greater<TestPairWithList>());

    std::vector<int> desc_result;
    printf("降序结果: ");
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        desc_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    bool is_descending = std::is_sorted(desc_result.begin(), desc_result.end(), std::greater<int>());
    EXPECT_TRUE(is_descending) << "降序排序应该正确";
    printf("降序验证: %s\n", is_descending ? "通过" : "失败");

    // 测试2: 自定义 lambda 比较器 (按key的奇偶性排序)
    printf("\n测试2: 自定义排序 (奇数优先)\n");
    ht->SortListMergeFast([](const TestPairWithList& a, const TestPairWithList& b)
    {
        // 奇数 < 偶数，相同奇偶性内部按升序
        bool a_odd = (a.key % 2 == 1);
        bool b_odd = (b.key % 2 == 1);
        if (a_odd != b_odd)
        {
            return a_odd > b_odd; // 奇数优先
        }
        return a.key < b.key; // 相同奇偶性按升序
    });

    std::vector<int> custom_result;
    printf("自定义结果: ");
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        custom_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    // 验证奇数在前
    bool found_even = false;
    bool custom_correct = true;
    for (int key : custom_result)
    {
        if (key % 2 == 0)
        {
            found_even = true;
        }
        else if (found_even)
        {
            // 发现偶数后又出现奇数，不正确
            custom_correct = false;
            break;
        }
    }
    EXPECT_TRUE(custom_correct) << "自定义排序应该正确（奇数在前）";
    printf("自定义验证: %s\n", custom_correct ? "通过" : "失败");

    // 测试3: 恢复升序排序
    printf("\n测试3: 恢复升序排序\n");
    ht->SortListMergeFast(); // 默认升序

    std::vector<int> asc_result;
    printf("升序结果: ");
    for (auto it = ht->list_begin(); it != ht->list_end(); ++it)
    {
        asc_result.push_back(it->key);
        printf("%d ", it->key);
    }
    printf("\n");

    bool is_ascending = std::is_sorted(asc_result.begin(), asc_result.end());
    EXPECT_TRUE(is_ascending) << "升序排序应该正确";
    printf("升序验证: %s\n", is_ascending ? "通过" : "失败");

    printf("==============================================================\n\n");
}

// ==================== 搜索插入位置函数改进测试 ====================

/**
 * @brief 测试改进后的搜索插入位置函数基本功能
 * @note 验证LineSearchInsertPosition、BinarySearchInsertPosition、FastSearchInsertPosition和AdaptiveSearchInsertPosition的改进版本
 */
TEST(NFShmHashTableWithListTest, SearchInsertPositionBasicFunctionalityTest)
{
    typedef std::pair<int, std::string> KeyValue;
    struct KeyExtractor
    {
        int operator()(const KeyValue& kv) const { return kv.first; }
    };

    NFShmHashTableWithList<KeyValue, int, 100, std::hash<int>, KeyExtractor, std::equal_to<int>> ht;
    ASSERT_EQ(ht.CreateInit(), 0);

    // 键比较器
    auto comp = [](const KeyValue& a, const KeyValue& b) -> bool
    {
        return a.first < b.first;
    };

    // 插入测试数据
    std::vector<int> test_keys = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    for (int key : test_keys)
    {
        KeyValue pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 排序链表
    ht.SortList();

    // 获取一个节点用于测试
    auto node = ht.GetNode(0);
    if (node && node->m_valid)
    {
        KeyValue target(45, "target"); // 应该插入到末尾
        node->m_value = target;

        // 测试LineSearchInsertPosition
        auto line_result = ht.LineSearchInsertPosition(node, comp);

        // 测试BinarySearchInsertPosition
        auto binary_result = ht.BinarySearchInsertPosition(node, comp);

        // 测试FastSearchInsertPosition
        auto fast_result = ht.FastSearchInsertPosition(node, comp);

        // 测试AdaptiveSearchInsertPosition
        auto adaptive_result = ht.AdaptiveSearchInsertPosition(node, comp);

        printf("搜索插入位置函数基本功能测试完成\n");
        printf("  LineSearch result: %s\n", line_result ? "有效" : "nullptr");
        printf("  BinarySearch result: %s\n", binary_result ? "有效" : "nullptr");
        printf("  FastSearch result: %s\n", fast_result ? "有效" : "nullptr");
        printf("  AdaptiveSearch result: %s\n", adaptive_result ? "有效" : "nullptr");
    }
}

/**
 * @brief 测试不同数据规模下搜索插入位置函数的性能
 */
TEST(NFShmHashTableWithListTest, SearchInsertPositionPerformanceTest)
{
    typedef std::pair<int, std::string> KeyValue;
    struct KeyExtractor
    {
        int operator()(const KeyValue& kv) const { return kv.first; }
    };

    const std::vector<int> test_sizes = {10, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

    printf("==============================================================\n");
    printf("搜索插入位置函数性能测试\n");
    printf("==============================================================\n");

    for (int size : test_sizes)
    {
        NFShmHashTableWithList<KeyValue, int, 10000, std::hash<int>, KeyExtractor, std::equal_to<int>>* pHt = new NFShmHashTableWithList<KeyValue, int, 10000, std::hash<int>, KeyExtractor, std::equal_to<int>>();
        NFShmHashTableWithList<KeyValue, int, 10000, std::hash<int>, KeyExtractor, std::equal_to<int>>& ht = *pHt;
        ASSERT_EQ(ht.CreateInit(), 0);

        auto comp = [](const KeyValue& a, const KeyValue& b) -> bool
        {
            return a.first < b.first;
        };

        // 生成随机数据
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<int> dis(1, size * 10);

        std::vector<int> keys;
        for (int i = 0; i < size; ++i)
        {
            keys.push_back(dis(gen));
        }

        // 插入数据
        for (int key : keys)
        {
            KeyValue pair(key, "value" + std::to_string(key));
            ht.insert_unique(pair);
        }

        // 排序
        ht.SortList();

        // 准备测试目标
        auto node = ht.GetNode(0);
        if (node && node->m_valid)
        {
            // 测试各个函数的性能
            const int iterations = 10000;
            std::vector<KeyValue> targetVec;
            targetVec.resize(iterations);
            for (int i = 0; i < iterations; ++i)
            {
                KeyValue target(dis(gen), "target");
                targetVec[i] = target;
            }

            // LineSearchInsertPosition测试
            long long line_time = 0;
            for (int i = 0; i < iterations; ++i)
            {
                node->m_value = targetVec[i];
                auto start = std::chrono::high_resolution_clock::now();
                ht.LineSearchInsertPosition(node, comp);
                auto end = std::chrono::high_resolution_clock::now();
                line_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }


            // BinarySearchInsertPosition测试
            long long binary_time = 0;
            for (int i = 0; i < iterations; ++i)
            {
                node->m_value = targetVec[i];
                auto start = std::chrono::high_resolution_clock::now();
                ht.BinarySearchInsertPosition(node, comp);
                auto end = std::chrono::high_resolution_clock::now();
                binary_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // FastSearchInsertPosition测试
            long long fast_time = 0;
            for (int i = 0; i < iterations; ++i)
            {
                node->m_value = targetVec[i];
                auto start = std::chrono::high_resolution_clock::now();
                ht.FastSearchInsertPosition(node, comp);
                auto end = std::chrono::high_resolution_clock::now();
                fast_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            // AdaptiveSearchInsertPosition测试
            long long adaptive_time = 0;
            for (int i = 0; i < iterations; ++i)
            {
                node->m_value = targetVec[i];
                auto start = std::chrono::high_resolution_clock::now();
                ht.AdaptiveSearchInsertPosition(node, comp);
                auto end = std::chrono::high_resolution_clock::now();
                adaptive_time += std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
            }

            printf("数据规模: %d 元素\n", size);
            printf("  LineSearch: %lld μs (%d 次调用) - 平均 %.2f ns/次\n", line_time, iterations, (double)line_time * 1000.0 / iterations);
            printf("  BinarySearch: %lld μs (%d 次调用) - 平均 %.2f ns/次\n", binary_time, iterations, (double)binary_time * 1000.0 / iterations);
            printf("  FastSearch: %lld μs (%d 次调用) - 平均 %.2f ns/次\n", fast_time, iterations, (double)fast_time * 1000.0 / iterations);
            printf("  AdaptiveSearch: %lld μs (%d 次调用) - 平均 %.2f ns/次\n", adaptive_time, iterations, (double)adaptive_time * 1000.0 / iterations);

            // 计算相对性能
            long long min_time = std::min({line_time, binary_time, fast_time, adaptive_time});
            std::string fastest_algo;
            if (min_time == line_time)
                fastest_algo = "LineSearch";
            else if (min_time == binary_time)
                fastest_algo = "BinarySearch";
            else if (min_time == fast_time)
                fastest_algo = "FastSearch";
            else
                fastest_algo = "AdaptiveSearch";

            printf("  最快算法: %s (%lld μs)\n", fastest_algo.c_str(), min_time);
            printf("  性能对比 (相对于最快算法):\n");
            printf("    LineSearch: %.2fx", (double)line_time / min_time);
            if (line_time == min_time)
                printf(" ");
            printf("\n");
            printf("    BinarySearch: %.2fx", (double)binary_time / min_time);
            if (binary_time == min_time)
                printf(" ");
            printf("\n");
            printf("    FastSearch: %.2fx", (double)fast_time / min_time);
            if (fast_time == min_time)
                printf(" ");
            printf("\n");
            printf("    AdaptiveSearch: %.2fx", (double)adaptive_time / min_time);
            if (adaptive_time == min_time)
                printf(" ");
            printf("\n");

            // 理论复杂度分析
            printf("  理论复杂度分析:\n");
            printf("    LineSearch: O(n) = O(%d) - 实际最优(链表顺序访问)\n", size);
            printf("    BinarySearch: O(n+log n) = O(%d) - 需要先收集索引\n", size);
            printf("    FastSearch: O(n) = O(%d) - 优化的线性搜索\n", size);
            printf("  \n");
            printf("  算法特点分析:\n");
            printf("    LineSearch: 简单直接，缓存友好，最少开销\n");
            printf("    BinarySearch: 额外的索引收集开销，在链表上不适用\n");
            printf("    FastSearch: 批量处理优化，减少函数调用开销\n");

            // 性能建议
            if (size <= 300)
            {
                printf("  建议: 使用LineSearch (当前数据规模下最优)\n");
            }
            else if (size <= 1000)
            {
                printf("  建议: FastSearch可能有微小优势\n");
            }
            else
            {
                printf("  建议: 大数据集仍然推荐LineSearch\n");
            }
            printf("--------------------------------------------------------------\n");
        }
        delete pHt;
    }

    printf("==============================================================\n\n");
}

/**
 * @brief 测试搜索插入位置函数的边界情况
 */
TEST(NFShmHashTableWithListTest, SearchInsertPositionEdgeCasesTest)
{
    typedef std::pair<int, std::string> KeyValue;
    struct KeyExtractor
    {
        int operator()(const KeyValue& kv) const { return kv.first; }
    };

    NFShmHashTableWithList<KeyValue, int, 100, std::hash<int>, KeyExtractor, std::equal_to<int>> ht;
    ASSERT_EQ(ht.CreateInit(), 0);

    auto comp = [](const KeyValue& a, const KeyValue& b) -> bool
    {
        return a.first < b.first;
    };

    printf("==============================================================\n");
    printf("搜索插入位置函数边界情况测试\n");
    printf("==============================================================\n");

    // 测试空表
    printf("测试1: 空表情况\n");
    EXPECT_EQ(ht.LineSearchInsertPosition(nullptr, comp), nullptr);
    EXPECT_EQ(ht.BinarySearchInsertPosition(nullptr, comp), nullptr);
    EXPECT_EQ(ht.FastSearchInsertPosition(nullptr, comp), nullptr);
    EXPECT_EQ(ht.AdaptiveSearchInsertPosition(nullptr, comp), nullptr);
    printf("  空表测试通过\n");

    // 测试单元素
    printf("测试2: 单元素情况\n");
    KeyValue single(10, "single");
    ht.insert_unique(single);

    auto node = ht.GetNode(0);
    if (node && node->m_valid)
    {
        KeyValue target(5, "target");
        node->m_value = target;

        auto line_result = ht.LineSearchInsertPosition(node, comp);
        auto binary_result = ht.BinarySearchInsertPosition(node, comp);
        auto fast_result = ht.FastSearchInsertPosition(node, comp);
        auto adaptive_result = ht.AdaptiveSearchInsertPosition(node, comp);

        printf("  单元素测试完成\n");
        printf("    LineSearch: %s\n", line_result ? "找到位置" : "插入末尾");
        printf("    BinarySearch: %s\n", binary_result ? "找到位置" : "插入末尾");
        printf("    FastSearch: %s\n", fast_result ? "找到位置" : "插入末尾");
        printf("    AdaptiveSearch: %s\n", adaptive_result ? "找到位置" : "插入末尾");
    }

    // 测试边界值插入
    printf("测试3: 边界值插入\n");
    ht.clear();

    // 插入有序数据
    std::vector<int> sorted_keys = {1, 3, 5, 7, 9};
    for (int key : sorted_keys)
    {
        KeyValue pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    node = ht.GetNode(0);
    if (node && node->m_valid)
    {
        // 测试插入到开头
        KeyValue head_target(0, "head");
        node->m_value = head_target;
        auto head_result = ht.AdaptiveSearchInsertPosition(node, comp);
        printf("  插入到开头: %s\n", head_result ? "找到正确位置" : "插入末尾");

        // 测试插入到末尾
        KeyValue tail_target(10, "tail");
        node->m_value = tail_target;
        auto tail_result = ht.AdaptiveSearchInsertPosition(node, comp);
        printf("  插入到末尾: %s\n", tail_result ? "找到位置" : "插入末尾(正确)");

        // 测试插入到中间
        KeyValue middle_target(4, "middle");
        node->m_value = middle_target;
        auto middle_result = ht.AdaptiveSearchInsertPosition(node, comp);
        printf("  插入到中间: %s\n", middle_result ? "找到正确位置" : "插入末尾");
    }

    printf("==============================================================\n\n");
}

/**
 * @brief 测试搜索插入位置函数的正确性
 */
TEST(NFShmHashTableWithListTest, SearchInsertPositionCorrectnessTest)
{
    typedef std::pair<int, std::string> KeyValue;
    struct KeyExtractor
    {
        int operator()(const KeyValue& kv) const { return kv.first; }
    };

    NFShmHashTableWithList<KeyValue, int, 100, std::hash<int>, KeyExtractor, std::equal_to<int>> ht;
    ASSERT_EQ(ht.CreateInit(), 0);

    auto comp = [](const KeyValue& a, const KeyValue& b) -> bool
    {
        return a.first < b.first;
    };

    printf("==============================================================\n");
    printf("搜索插入位置函数正确性测试\n");
    printf("==============================================================\n");

    // 插入排序的数据
    std::vector<int> sorted_keys = {1, 3, 5, 7, 9, 11, 13, 15};
    for (int key : sorted_keys)
    {
        KeyValue pair(key, "value" + std::to_string(key));
        ht.insert_unique(pair);
    }

    // 测试插入位置的正确性
    auto node = ht.GetNode(0);
    if (node && node->m_valid)
    {
        // 测试各种插入位置
        std::vector<int> test_values = {0, 2, 4, 6, 8, 10, 12, 14, 16};

        int correct_positions = 0;
        int total_tests = 0;

        for (int val : test_values)
        {
            KeyValue target(val, "target");
            node->m_value = target;

            auto line_result = ht.LineSearchInsertPosition(node, comp);
            auto binary_result = ht.BinarySearchInsertPosition(node, comp);
            auto fast_result = ht.FastSearchInsertPosition(node, comp);
            auto adaptive_result = ht.AdaptiveSearchInsertPosition(node, comp);

            // 验证插入位置的合理性
            bool line_valid = true;
            bool binary_valid = true;
            bool fast_valid = true;
            bool adaptive_valid = true;

            if (line_result)
            {
                line_valid = (line_result->m_value.first >= val);
            }
            if (binary_result)
            {
                binary_valid = (binary_result->m_value.first >= val);
            }
            if (fast_result)
            {
                fast_valid = (fast_result->m_value.first >= val);
            }
            if (adaptive_result)
            {
                adaptive_valid = (adaptive_result->m_value.first >= val);
            }

            if (line_valid && binary_valid && fast_valid && adaptive_valid)
            {
                correct_positions++;
            }

            total_tests++;

            printf("测试值 %d: Line(%s) Binary(%s) Fast(%s) Adaptive(%s)\n", val, line_valid ? "√" : "×", binary_valid ? "√" : "×", fast_valid ? "√" : "×", adaptive_valid ? "√" : "×");
        }

        printf("--------------------------------------------------------------\n");
        printf("正确性测试结果: %d/%d 通过 (%.1f%%)\n", correct_positions, total_tests, (double)correct_positions / total_tests * 100.0);
    }

    printf("==============================================================\n\n");
}

/**
 * @brief 测试自适应策略在不同数据规模下的选择
 */
TEST(NFShmHashTableWithListTest, AdaptiveStrategySelectionTest)
{
    typedef std::pair<int, std::string> KeyValue;
    struct KeyExtractor
    {
        int operator()(const KeyValue& kv) const { return kv.first; }
    };

    printf("==============================================================\n");
    printf("自适应策略选择测试\n");
    printf("==============================================================\n");

    auto comp = [](const KeyValue& a, const KeyValue& b) -> bool
    {
        return a.first < b.first;
    };

    // 测试不同数据规模下的策略选择
    std::vector<int> sizes = {5, 20, 50, 150, 300, 600};

    for (int size : sizes)
    {
        NFShmHashTableWithList<KeyValue, int, 1000, std::hash<int>, KeyExtractor, std::equal_to<int>> ht;
        ASSERT_EQ(ht.CreateInit(), 0);

        // 插入数据
        for (int i = 0; i < size; ++i)
        {
            KeyValue pair(i * 2, "value" + std::to_string(i));
            ht.insert_unique(pair);
        }

        ht.SortList();

        auto node = ht.GetNode(0);
        if (node && node->m_valid)
        {
            KeyValue target(size + 1, "target");
            node->m_value = target;

            // 测试自适应策略
            const int test_iterations = 100;

            auto start = std::chrono::high_resolution_clock::now();
            for (int i = 0; i < test_iterations; ++i)
            {
                ht.AdaptiveSearchInsertPosition(node, comp);
            }
            auto end = std::chrono::high_resolution_clock::now();
            auto adaptive_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();

            // 预期的策略选择
            std::string expected_strategy;
            if (size <= 16)
            {
                expected_strategy = "LineSearch";
            }
            else if (size <= 128)
            {
                expected_strategy = "BinarySearch";
            }
            else if (size <= 512)
            {
                expected_strategy = "FastSearch";
            }
            else
            {
                expected_strategy = "LineSearch (回退)";
            }

            printf("数据规模: %d, 预期策略: %s, 性能: %lld μs\n", size, expected_strategy.c_str(), adaptive_time);
        }
    }

    printf("==============================================================\n\n");
}

// ==================== move_to_list_sorted 测试（修正版本） ====================

/**
 * @brief 为了方便测试排序，创建一个带有多个字段的测试结构
 * @note key 字段用于哈希表，priority 和 name 字段用于排序比较
 */
struct TestMultiFieldPair
{
    int key;
    int priority; // 用于排序的字段1
    std::string name; // 用于排序的字段2
    double value; // 用于排序的字段3

    TestMultiFieldPair() : key(0), priority(0), name(""), value(0.0)
    {
    }

    TestMultiFieldPair(int k, int p, const std::string& n, double v = 0.0) : key(k), priority(p), name(n), value(v)
    {
    }

    // 重载操作符用于默认比较
    bool operator<(const TestMultiFieldPair& other) const
    {
        // 默认按priority排序，priority相同则按name排序
        if (priority != other.priority)
            return priority < other.priority;
        return name < other.name;
    }

    bool operator==(const TestMultiFieldPair& other) const
    {
        return key == other.key;
    }
};

namespace std
{
    template <>
    struct hash<TestMultiFieldPair>
    {
        size_t operator()(const TestMultiFieldPair& value) const
        {
            return NFHash::hash_combine(value.key);
        }
    };
}

/**
 * @brief 测试 move_to_list_sorted 基本功能（修正版本）
 * @note 遵循新的约束：1) 使用前先SortList() 2) 不修改key，只基于其他字段排序
 */
TEST(NFShmHashTableWithListTest, MoveToListSortedBasicCorrect)
{
    printf("========== Testing move_to_list_sorted Basic (Corrected) ==========\n");

    typedef NFShmHashTableWithList<NFShmPair<int, TestMultiFieldPair>, int, 100, std::hash<int>, std::_Select1st<NFShmPair<int, TestMultiFieldPair>>, std::equal_to<int>> HashTableType;
    HashTableType ht;
    ht.CreateInit();

    // 插入测试数据 - key值固定，priority和name用于排序
    std::vector<TestMultiFieldPair> test_data = {
        TestMultiFieldPair(1, 30, "zebra", 1.0), // key=1, priority=30
        TestMultiFieldPair(2, 10, "apple", 2.0), // key=2, priority=10
        TestMultiFieldPair(3, 50, "banana", 3.0), // key=3, priority=50
        TestMultiFieldPair(4, 20, "cherry", 4.0), // key=4, priority=20
        TestMultiFieldPair(5, 40, "date", 5.0) // key=5, priority=40
    };

    for (const auto& pair : test_data)
    {
        ht.insert_unique(NFShmPair<int, TestMultiFieldPair>(pair.key, pair));
    }

    printf("插入后的初始顺序: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
    }
    printf("\n");

    // *** 重要：使用move_to_list_sorted前，必须先SortList()确保链表有序 ***
    printf("调用SortList()确保链表按priority有序...\n");
    ht.SortList([](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
    {
        return a.second.priority < b.second.priority; // 按priority升序排序，不涉及key
    });

    printf("SortList()后的顺序: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
    }
    printf("\n");

    // 现在可以安全使用move_to_list_sorted
    // 测试1: 修改key=3的元素的priority，然后移动到正确位置
    auto target_it = ht.find(3);
    if (target_it != ht.end())
    {
        printf("修改key=3的priority从50到15，然后使用move_to_list_sorted重新定位...\n");

        // 重要：只修改非key字段，不修改key字段
        const_cast<TestMultiFieldPair*>(&(target_it->second))->priority = 15;

        // 使用move_to_list_sorted重新定位（基于priority排序，不涉及key）
        ht.move_to_list_sorted(target_it, [](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
        {
            return a.second.priority < b.second.priority;
        });

        printf("move_to_list_sorted后的顺序: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
        }
        printf("\n");
    }

    printf("========== move_to_list_sorted Basic Test (Corrected) Completed ==========\n\n");

    // 验证最终结果的正确性
    std::vector<int> expected_order = {2, 1, 4, 5, 3}; // 按priority顺序：10->15->20->40->50
    std::vector<int> actual_order;
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        actual_order.push_back(it->second.key);
    }

    // 验证链表大小
    EXPECT_EQ(ht.size(), 5) << "链表大小应该为5";
    EXPECT_EQ(actual_order.size(), 5) << "实际遍历的元素数量应该为5";
}

/**
 * @brief 测试 move_to_list_sorted 和 SortList() 的性能比较（修正版本）
 * @note 比较在已排序链表中单个元素重定位 vs 全表重排序的性能
 */
TEST(NFShmHashTableWithListTest, MoveToListSortedVsSortListPerformanceCorrect)
{
    printf("========== Performance Comparison: move_to_list_sorted vs SortList (Corrected) ==========\n");

    typedef NFShmHashTableWithList<NFShmPair<int, TestMultiFieldPair>, int, 2000, std::hash<int>, std::_Select1st<NFShmPair<int, TestMultiFieldPair>>, std::equal_to<int>> HashTableType;
    std::vector<int> test_sizes = {100, 500, 1000};

    printf("%-8s %-15s %-20s %-20s %-15s\n", "Size", "Method", "Time(ns)", "Ops/sec", "Notes");
    printf("%-8s %-15s %-20s %-20s %-15s\n", "----", "-------------", "------------------", "------------------", "---------");

    for (int size : test_sizes)
    {
        auto ht1 = std::make_unique<HashTableType>();
        auto ht2 = std::make_unique<HashTableType>();
        ht1->CreateInit();
        ht2->CreateInit();

        // 插入有序数据（按priority排序）
        for (int i = 0; i < size; ++i)
        {
            TestMultiFieldPair pair1(i, i * 2, "name" + std::to_string(i * 2), i * 1.5);
            TestMultiFieldPair pair2(i, i * 2, "name" + std::to_string(i * 2), i * 1.5);
            ht1->insert_unique(NFShmPair<int, TestMultiFieldPair>(pair1.key, pair1));
            ht2->insert_unique(NFShmPair<int, TestMultiFieldPair>(pair2.key, pair2));
        }

        // *** 重要：测试前先确保链表有序 ***
        auto priority_comp = [](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
        {
            return a.second.priority < b.second.priority;
        };

        ht1->SortList(priority_comp);
        ht2->SortList(priority_comp);

        // 选择中间的元素进行修改
        int target_key = size / 2;
        auto target_it1 = ht1->find(target_key);
        auto target_it2 = ht2->find(target_key);

        if (target_it1 != ht1->end() && target_it2 != ht2->end())
        {
            // 修改priority值（模拟需要重新排序的场景）
            const_cast<TestMultiFieldPair*>(&(target_it1->second))->priority = 1; // 移动到前面
            const_cast<TestMultiFieldPair*>(&(target_it2->second))->priority = 1;

            // 测试move_to_list_sorted性能（单个元素重定位）
            auto start = std::chrono::high_resolution_clock::now();
            ht1->move_to_list_sorted(target_it1, priority_comp);
            auto end = std::chrono::high_resolution_clock::now();
            long long move_time = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

            // 测试SortList性能（全表重排序）
            start = std::chrono::high_resolution_clock::now();
            ht2->SortList(priority_comp);
            end = std::chrono::high_resolution_clock::now();
            long long sort_time = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

            // 计算操作速度
            double move_ops_per_sec = move_time > 0 ? 1000000000.0 / move_time : 999999;
            double sort_ops_per_sec = sort_time > 0 ? 1000000000.0 / sort_time : 999999;

            printf("%-8d %-15s %-20lld %-20.0f %-15s\n", size, "move_to_sorted", move_time, move_ops_per_sec, "Single elem");
            printf("%-8d %-15s %-20lld %-20.0f %-15s\n", size, "SortList", sort_time, sort_ops_per_sec, "Full sort");

            // 验证两种方法的结果是否一致
            bool results_match = true;
            auto it1 = ht1->list_begin();
            auto it2 = ht2->list_begin();
            while (it1 != ht1->list_end() && it2 != ht2->list_end())
            {
                if (it1->second.key != it2->second.key || it1->second.priority != it2->second.priority)
                {
                    results_match = false;
                    break;
                }
                ++it1;
                ++it2;
            }

            printf("%-8s %-15s %-20s %-20s %-15s\n", "", "Results Match", results_match ? "YES" : "NO", "", "");
            printf("\n");

            // 添加单元测试断言
            EXPECT_TRUE(results_match) << "move_to_list_sorted和SortList的结果应该一致，测试数据大小：" << size;
            EXPECT_GT(move_time, 0) << "move_to_list_sorted执行时间应该大于0";
            EXPECT_GT(sort_time, 0) << "SortList执行时间应该大于0";
        }
    }

    printf("总结: move_to_list_sorted适用于已排序链表中的单个元素重定位，\n");
    printf("      SortList()适用于大量数据变化后的全表重排序。\n");
    printf("      时间单位：纳秒(ns)，精度更高适合微小操作的性能分析。\n");
    printf("========== Performance Comparison Completed ==========\n\n");
}

/**
 * @brief 测试key值不可修改的约束
 * @note 验证排序操作只能基于非key字段
 */
TEST(NFShmHashTableWithListTest, KeyImmutabilityConstraint)
{
    printf("========== Testing Key Immutability Constraint ==========\n");

    typedef NFShmHashTableWithList<NFShmPair<int, TestMultiFieldPair>, int, 100, std::hash<int>, std::_Select1st<NFShmPair<int, TestMultiFieldPair>>, std::equal_to<int>> HashTableType;
    HashTableType ht;
    ht.CreateInit();

    // 插入测试数据
    std::vector<TestMultiFieldPair> test_data = {TestMultiFieldPair(1, 10, "alpha", 1.0), TestMultiFieldPair(2, 20, "beta", 2.0), TestMultiFieldPair(3, 30, "gamma", 3.0)};

    for (const auto& pair : test_data)
    {
        ht.insert_unique(NFShmPair<int, TestMultiFieldPair>(pair.key, pair));
    }

    printf("初始数据: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
    }
    printf("\n");

    // 先排序确保链表有序
    ht.SortList([](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
    {
        return a.second.priority < b.second.priority;
    });

    printf("按priority排序后: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
    }
    printf("\n");

    // 验证：修改非key字段后使用move_to_list_sorted - 这是允许的
    auto target_it = ht.find(2);
    if (target_it != ht.end())
    {
        printf("修改key=2的priority从20到5（只修改非key字段）...\n");
        const_cast<TestMultiFieldPair*>(&(target_it->second))->priority = 5;

        ht.move_to_list_sorted(target_it, [](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
        {
            return a.second.priority < b.second.priority;
        });

        printf("move_to_list_sorted后: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
        }
        printf("\n");
    }

    // 演示key值的不可变性：key值只用于哈希定位，不参与排序
    printf("验证key值不参与排序比较:\n");

    // 基于value字段排序（忽略key值）
    ht.SortList([](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
    {
        return a.second.value > b.second.value; // 按value降序，完全忽略key
    });

    printf("按value降序排序后: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,value=%.1f) ", it->second.key, it->second.priority, it->second.value);
    }
    printf("\n");

    printf("结论: key值只用于哈希定位和查找，排序操作完全基于其他字段。\n");
    printf("========== Key Immutability Constraint Test Completed ==========\n\n");

    // 验证数据完整性
    EXPECT_EQ(ht.size(), 3) << "应该有3个元素";

    // 验证key值确实没有被修改（仍然可以通过key找到元素）
    EXPECT_NE(ht.find(1), ht.end()) << "key=1的元素应该存在";
    EXPECT_NE(ht.find(2), ht.end()) << "key=2的元素应该存在";
    EXPECT_NE(ht.find(3), ht.end()) << "key=3的元素应该存在";

    // 验证只有非key字段被修改
    auto iter_2 = ht.find(2);
    EXPECT_EQ(iter_2->second.key, 2) << "key值应该保持不变";
    EXPECT_EQ(iter_2->second.priority, 5) << "priority应该被修改为5";
}

/**
 * @brief 测试在各种边界情况下的正确性
 * @note 验证SortList()调用前后move_to_list_sorted的行为
 */
TEST(NFShmHashTableWithListTest, MoveToListSortedEdgeCasesCorrect)
{
    printf("========== Testing move_to_list_sorted Edge Cases (Corrected) ==========\n");

    typedef NFShmHashTableWithList<NFShmPair<int, TestMultiFieldPair>, int, 100, std::hash<int>, std::_Select1st<NFShmPair<int, TestMultiFieldPair>>, std::equal_to<int>> HashTableType;
    HashTableType ht;
    ht.CreateInit();

    // 测试1: 空链表
    printf("测试1: 空链表情况\n");
    printf("链表大小: %zu\n", ht.size());
    EXPECT_EQ(ht.size(), 0) << "空链表大小应该为0";
    printf("空链表测试通过。\n\n");

    // 测试2: 单个元素
    printf("测试2: 单个元素情况\n");
    TestMultiFieldPair single_pair(1, 10, "single", 1.0);
    ht.insert_unique(NFShmPair<int, TestMultiFieldPair>(single_pair.key, single_pair));

    EXPECT_EQ(ht.size(), 1) << "插入一个元素后大小应该为1";

    // 先排序（虽然只有一个元素）
    ht.SortList([](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
    {
        return a.second.priority < b.second.priority;
    });

    auto it = ht.find(1);
    EXPECT_NE(it, ht.end()) << "应该能找到key=1的元素";

    if (it != ht.end())
    {
        // 修改priority并移动
        const_cast<TestMultiFieldPair*>(&(it->second))->priority = 20;
        ht.move_to_list_sorted(it, [](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
        {
            return a.second.priority < b.second.priority;
        });

        EXPECT_EQ(it->second.priority, 20) << "priority应该被修改为20";
    }

    printf("单个元素测试通过，元素: (key=%d,priority=%d)\n\n", it->second.key, it->second.priority);

    // 测试3: 相同priority值的处理
    printf("测试3: 相同priority值的处理\n");
    ht.clear();
    EXPECT_EQ(ht.size(), 0) << "clear后大小应该为0";

    std::vector<TestMultiFieldPair> same_priority_data = {TestMultiFieldPair(1, 10, "alpha", 1.0), TestMultiFieldPair(2, 10, "beta", 2.0), TestMultiFieldPair(3, 10, "gamma", 3.0), TestMultiFieldPair(4, 15, "delta", 4.0)};

    for (const auto& pair : same_priority_data)
    {
        ht.insert_unique(NFShmPair<int, TestMultiFieldPair>(pair.key, pair));
    }

    EXPECT_EQ(ht.size(), 4) << "插入4个元素后大小应该为4";

    // 先按priority排序，priority相同时按name排序
    ht.SortList([](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
    {
        if (a.second.priority != b.second.priority)
            return a.second.priority < b.second.priority;
        return a.second.name < b.second.name;
    });

    printf("初始排序（priority+name）: ");
    for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
    {
        printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
    }
    printf("\n");

    // 修改其中一个相同priority元素的name
    auto target = ht.find(2);
    EXPECT_NE(target, ht.end()) << "应该能找到key=2的元素";

    if (target != ht.end())
    {
        printf("修改key=2的name从'beta'到'zebra'...\n");
        std::string old_name = target->second.name;
        const_cast<TestMultiFieldPair*>(&(target->second))->name = "zebra";

        ht.move_to_list_sorted(target, [](const NFShmPair<int, TestMultiFieldPair>& a, const NFShmPair<int, TestMultiFieldPair>& b)
        {
            if (a.second.priority != b.second.priority)
                return a.second.priority < b.second.priority;
            return a.second.name < b.second.name;
        });

        printf("move_to_list_sorted后: ");
        for (auto it = ht.list_begin(); it != ht.list_end(); ++it)
        {
            printf("(key=%d,priority=%d,name=%s) ", it->second.key, it->second.priority, it->second.name.c_str());
        }
        printf("\n");

        // 验证name确实被修改
        EXPECT_EQ(target->second.name, "zebra") << "name应该被修改为zebra";
        EXPECT_NE(target->second.name, old_name) << "name应该不同于原来的值";
        EXPECT_EQ(target->second.key, 2) << "key应该保持不变";
    }

    printf("========== move_to_list_sorted Edge Cases Test (Corrected) Completed ==========\n\n");
}
